P4912
-
题意：给定 \(n\) 种魔法，每个魔法的长度为 \(a\)，威力为 \(b\)，如果一个魔法 \(j\) 在另一个魔法 \(i\) 后使用则威力增加 \(w(i,j)\)。给定长度 \(m\)，使得总长度为 \(m\) 并且威力最大，求威力的最大值。如果不能满足长度为 \(m\)，则输出 \(-1\)。
-
做法：背包 DP，动态转移方程为
\(f(i,j)=\max(f(i,j),f(k,j-a_i)+b_i+w(k,i))\)
注意，题目数据范围中 \(a\)，\(b\)，\(w_{i,j}\) 与 \(m\) 都有可能为负数，所以应该都加一个数使其成为正数。
- 代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=4e3;
int a[60],b[60],w[60][60],f[60][maxn+maxn];
int t=1145;//加一个数使得各数不为负数
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>a[i]>>b[i];
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
cin>>w[i][j];
memset(f,0xcf,sizeof(f));
f[0][t]=0;//初始化
for(int i=1;i<=n;++i)
{
for(int j=a[i];j<maxn+t;j++)
for(int k=0;k<i;++k)
if(f[k][j-a[i]]!=f[0][0])
f[i][j]=max(f[i][j],f[k][j-a[i]]+b[i]+w[k][i]);
}
int ans=f[0][0];
for(int i=0;i<=n;++i)
ans=max(ans,f[i][m+t]);
if(ans!=f[0][0])
cout<<ans;
else
cout<<-1;
}