题解 | H Nazrin the Greeeeeedy Mouse

思路:首先考虑到$siz{e}_{i+1}>siz{e}_{i}size\_\{i+1\}>\; size\_i$，所以当$m>nm>n$时，只用保留最后$nn$次即可。(前面的操作都取不到奶酪，可以去除 ) 接下来发现，每次操作一定是拿 走或破坏一个前缀的奶酪，所以如果我们知道了一个区间用大小为所少的包至多可以获得多少价值的奶 酪的话，可以写出 $d{p}_{i,j}dp\_\{i,j\}$表示当前已经拿走/破坏到了第i个奶酪，并且进行到了第j个操作，然后我们发现预处理可以使用区间转移:定义$f_{i,j,k}f\_\{i,j,k\}$表示区间 i至j 背包容量为k时能获取的最大质量,转移类似背包。 DP转移： $d{p}_{i,j}={\sum }_{k=1}^{j}max(d{p}_{i-1,k}+f_{k+1,i,chees{e}_i})dp\_\{i,j\}=\backslash sum\_\{k=1\}^j\; max(dp\_\{i-1,k\}+f\_\{k+1,i,cheese\_i\})$ 。 转移就相当于背包新加入一个物品。总时间复杂度为$O(n^3)O(n^3)$

$\mathrm{代}\mathrm{码}:代码:$

#define LL long long
using namespace std;
const int M=1e5+7;
int n,m;
int a[203],b[M],siz[M],all[M],tot=0;
int dp[203][203],f[203][203][203];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=m;i++){
        cin>>all[i];
    }
    if(m>=n){
        for(int i=m-n+1;i<=m;i++){
            siz[++tot]=all[i];
        }
    } else {
        for(int i=1;i<=m;i++){
            siz[i]=all[i];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            for(int k=0;k<=200;k++){
                if(k-a[j]>=0) f[i][j][k]=max(f[i][j-1][k],f[i][j-1][k-a[j]]+b[j]);
                else f[i][j][k]=f[i][j-1][k];
                //cout<<f[i][j][k]<<" ";
            }
        }
        //cout<<"\n";
    }
    int l,r,s;
//  while(cin>>l>>r>>s)
//      cout<<f[l][r][s]<<"\n";
    for(int i=1;i<=min(n,m);i++){
        for(int j=1;j<=n;j++){
            for(int k=0;k<j;k++){
                dp[i][j]=max(dp[i][j],dp[i-1][k]+f[k+1][j][siz[i]]);
            }
        }
    }
    int anq=0;
    for(int i=1;i<=n;i++){
        anq=max(anq,dp[min(m,n)][i]);
    }
    cout<<anq<<"\n";
}