萌新请教。#5为什么不过

CF19B Checkout Assistant

_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行 cnt+t[i]cnt+t[i]+1 的话,#5过,#4不过


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)


|