[题解] Luogu P2113 看球泡妹子
这题一开始看上去一脸不可做..... 感觉背包会爆炸
然后后面被甩一脸背包正解
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 许可协议 进行许可☆