自动搬运

查看原文

来自洛谷，原作者为

	koishi_offical 每一个人,都将成为我们的兄弟； 没有危险,没有苦难应该施加在我们身上。 我们将像我们的父辈一样成为自由之人， 苛苟为奴不如趁早拥抱死亡

搬运于2025-08-24 22:05:12，当前版本为作者最后更新于2021-03-31 13:58:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意分析

再看一下题意：有 $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;
}