_ruiniyan_ @ 2021-08-12 22:12:22
如题。
代码如下(样例已过)
#include<bits/stdc++.h>
#define X 2047
using namespace std;
long long N,T,C,w[X],t[X],f[X][X];
int main(){
cin>>N;
for(int i=1;i<=N;i++){
cin>>t[i]>>w[i];
T+=t[i];
C+=w[i];
}
for(int i=1;i<=N;i++){
for(int cnt=0;cnt<=T;cnt++){//cnt表示可以带走物品数量
if(cnt>=1) f[i][cnt]=max(f[i-1][cnt-1]+w[i],f[i-1][cnt+t[i]]);//偷走:可带数量减少了1个,获得w[i]价值;付钱:多出t[i]时间可偷
else f[i][cnt]=f[i-1][cnt+t[i]];
}
}
cout<<C-f[N][0];
}
by _ruiniyan_ @ 2021-08-12 22:16:49
15行
by dksx @ 2021-08-12 22:24:35
啊这,其实这就是个背包,然后就只是多了个判断时间,确定完状态了,就直接扣除扫描时间然后比较就ok了,至于#5不过你得先往背包放一个极大的值,像16fffffff 之类的
by _ruiniyan_ @ 2021-08-13 09:28:53
不行吧@dksx (?)
by dksx @ 2021-08-13 13:59:19
@k3sc03 太行了(doge)