社区讨论
为什么f数组范围改大就过了?玄关求助
B3873[GESP202309 六级] 小杨买饮料参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mhz46qhr
- 此快照首次捕获于
- 2025/11/15 01:10 4 个月前
- 此快照最后确认于
- 2025/11/16 13:44 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
long long n,L,ans=1e9,tot;
long long c[505],l[505];
long long f[505][4005];
int main(){
cin>>n>>L;
for(int i=1;i<=n;i++){
cin>>c[i]>>l[i];
tot+=l[i];
}
if(tot<L) {
cout<<"no solution"<<endl;
return 0;
}
for(int i=0;i<=n+1;i++)
for(int j=0;j<=L*2;j++){
f[i][j]=1e9;
}
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<l[i];j++){//此时无法选择当前饮料,只能继承前i-1个物品的结果
f[i][j]=f[i-1][j];
}
for(int j=l[i];j<=L*2;j++){
f[i][j]=min(f[i-1][j],f[i-1][j-l[i]]+c[i]);
}
}
for(int i=1;i<=n;i++){
if(l[i]>=L){
if(c[i]<ans) {
ans=c[i];
}
}
}
for(int i=L;i<=2*L;i++){
ans=min(ans,f[n][i]);
}
cout<<ans<<'\n';
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...