p4912 帕秋莉的魔法 题解

· · 题解

题意分析

再看一下题意：有 n 段膜法，每段膜法有一个长度 a，威力 b。如果一个膜法 j 在另一个膜法 i（i<j） 后释放，威力增加 w(i,j)。给你一个长度 m，释放一堆膜法，使得膜法总长度为 m，且膜法的总威力最大，求膜法威力的最大值，如果不能满足长度为 m，则输出 -1。

看起来乱七八糟，让我们把东方语翻译成 OI 语。

有 n 个物品和一个容量为 m 的背包，每个物品有一个体积 a 价值 b；

如果一个物品 j 在物品 i 后放进背包,价值增加 w(i,j)；

求使背包恰好装满的情况下，最大的价值总和，如果背包无法恰好装满，输出 -1。

很明显的一个背包问题。

那么状态转移方程式显而易见。

设 在前 i 个物品里取，且总长度恰好为 j （注意是恰好，这是一般的背包不太一样）的最大价值为 f(i,j)

f(i,j)=\max(f(k,j-a(i))+b(i)+w(k,i)) (0<k<i)

初始状态 f(0,0)=0

但是，如果按照这个思路写，就会 WA。

为什么？因为帕秋莉有了咲夜的帮助，使得一段膜法的长度可以为负数，

所以我们要将所有状态都向右位移一个值 mov。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=60,M=5e3;
int n,m;
int a[N],b[N],w[N][N],mov=2501;
int f[N][M+M];
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][mov]=0;
    for(int i=1;i<=n;i++)
      {
         for(int j=a[i];j<M+mov;j++)//因为a[i]可以为负数，所以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+mov]);
    if(ans!=f[0][0]) cout<<ans;
    else cout<<-1;
}