这题一开始看上去一脸不可做..... 感觉背包会爆炸
然后后面被甩一脸背包正解

Problem

多个单件物品，保证 v[i]>= c 的情况下，使 w[i]最大

Solution

令 dpi[k]为前 i 个物品，用了 j 个物品，v[i]的累计值为 k
由于 k 只需大于等于 c，因此 >= c 的 k 值我们都压缩到 dpi[c]

然后普通的转移就行了。01 背包问题那样。
由于压缩，本题转移可能还有点鬼。

空间复杂度上，第一维大概可以滚动掉。

Code

// Code by ajcxsu
// Problem: Luogu P2113

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

const int N=101,C=1010;
int dp[N][N][C];
int str[N],cool[N];
int w[N],v[N];
int n,m,k,c;

int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m>>k>>c;
    for(int i=1;i<=n;i++) cin>>str[i];
    for(int i=1;i<=n;i++) cin>>cool[i];
    int a,b;
    for(int i=1;i<=m;i++) {
        cin>>a>>b;
        w[i]=str[a]*str[b], v[i]=cool[a]+cool[b];
    }
    
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0][0]=0;
    int ans=-1;
    for(int i=1;i<=m;i++) {
        for(int j=0;j<=k;j++) {
            for(int kk=0;kk<=c;kk++) {
                dp[i][j][kk]=dp[i-1][j][kk];
                if(j && kk>=v[i]) dp[i][j][kk]=max(dp[i][j][kk], dp[i-1][j-1][kk-v[i]] + w[i]);
            }
            for(int kk=max(c-v[i]+1,0);j && kk<=c;kk++) 
                dp[i][j][c]=max(dp[i][j][c], dp[i-1][j-1][kk] + w[i]);
            if(i==m) ans=max(ans,dp[i][j][c]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol_luogu_2113.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆