[USACO3.4] Raucous Rockers

有 (n) 个物品依次出现，你需要把它们依次装进 (m) 个包。第 (i) 个包中装的物品的出现次序必须都在第 (i-1) 个包之后。物品可以放弃。物品有体积，包有容量 (t)。求可以装的物品的最大数目。(n,m,t leq 20)

Solution

设 (f[i][j][k]) 表示考虑了前 (i) 个物品，正在装第 (j) 个包，这个包被装了 (k) 体积时的最大收益

转移无非就是考虑换一个新的包，决策装不装这个物品

#include <bits/stdc++.h>
using namespace std;

int n,t,m,f[25][25][25],a[25];

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>t>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            for(int k=0;k<a[i];k++) f[i][j][k]=f[i-1][j][k];
            for(int k=a[i];k<=t;k++) {
                f[i][j][k]=max(f[i-1][j][k],max(f[i-1][j-1][t],f[i-1][j][k-a[i]])+1);
                ans=max(ans,f[i][j][k]);
            }
        }
    }
    cout<<ans;
}