本文共 993 字，大约阅读时间需要 3 分钟。
对于每座堡垒，将$s$个对手排序，显然如果安排的兵力能打败第$i$个对手就一定能打败前$i-1$个。
那么对于第$i$座城堡，可以看做有$s+1$个物品(可以不安排兵力)，第$j$个物品代价为$2*v[j]+1$，收益为$i*j$。
剩下的只需要将每座城堡的所有物品放在一组然后分组背包即可。
#include #include #include #include #include #include #include #include #include #include #include using namespace std;int f[120][20010];int cnt[120];int g[120][120];int h[120][120];int s[120];int mp[120][120];int n,m,k;int main(){ scanf("%d%d%d",&k,&n,&m); for(int i=1;i<=k;i++) { for(int j=1;j<=n;j++) { scanf("%d",&mp[i][j]); } } for(int i=1;i<=n;i++) { for(int j=1;j<=k;j++) { s[j]=mp[j][i]; } sort(s+1,s+1+k); for(int j=1;j<=k;j++) { if(2*s[j]+1<=m) { g[i][++cnt[i]]=2*s[j]+1; h[i][cnt[i]]=i*j; } } } for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { for(int k=0;k<=cnt[i];k++) { if(j>=g[i][k]) { f[i][j]=max(f[i][j],f[i-1][j-g[i][k]]+h[i][k]); } } } } printf("%d",f[n][m]);}
转载于:https://www.cnblogs.com/Khada-Jhin/p/10772297.html