题意

题目链接

有 $n$ 种有体积和价值的物品和一个容量为 $m$ 的背包，每种物品有无数多个。

记第 $i$ 中物品最终在背包里放了 $a_i$ 个，我们需要这个答案序列先单调非降再单调非升，即有一个 $k$ 使得答案数列呈现 $a_1\le a_2\le \dots \le a_k \ge \dots \ge a_n$。

对于每一个背包容量 $1,2,3,\dots,m$，在使得背包能够装下最大价值总和的物品的情况下，求一个最小的 $k$​ 以及对应的最大价值总和。

$1\le n \le 2000,1\le m \le 500$

解析

我们先考虑 easy version，即 $k$ 是给定的值的情况。

我们发现可以把所有物品拆解为 $1\sim k，2\sim k,\dots k\sim k,1\sim k+1,2\sim k+1\dots 1\sim n,2\sim n\dots k\sim n$ 这么多物品，我们用这些物品跑完全背包，结果显然是符合要求的。看似时间复杂度为 $O(n^2m)$，但是由于体积不为零，所以超过 $500$ 个数量的物品是无效的，实际时间复杂度为 $O(nm^2)$。

然后再回到 hard version，我们发现对于相邻的两个数作为 $k$，他们的物品重合度是很高的，所以我们考虑有没有方法可以减少更新次数。记 $f_{i,j}$ 为以 $i$ 点为 $k$，体积为 $j$ 的最大价值，有一个很神奇的式子 $f_{i,j}=\max{f_{i,j},f_{i+1,j},f_{i,j-W}+V}$，再更新过程中，我们先从左往右枚举 $i$ 作为左端点，再从右往左枚举 $j$ 更新 $f_{j,x}$，更新的是 $i \sim j$ 的所有物品组成的一个复合物品，这部分代码如下：

for(int i=1;i<=n;i++){
    for(int j=n;j>=i;j--){
        ll W=w[j]-w[i-1];//此处为前缀和
        ll V=v[j]-v[i-1];//此处为前缀和
        for(int k=W;k<=m;k++){
            f[j][k]=max({f[j][k],f[j+1][k],f[j][k-W]+V});
        }
    }
    for(int j=1;j<=m;j++){
        if(f[i][j]>ans[j]){
            ans[j]=f[i][j];
            ansid[j]=i;
        }
    }
}

你发现，对于 $f_{j,k}$，以这样的遍历方式，必然有 $f_{j+1,k}$ 中考虑过的数都在 $f_{j,k}$ 的考虑范围内。但这一式子真的不会有疏漏吗？其实是有的，但是无所谓，原因是这样的：

假设我们遍历到 $i,j$，则 $f_{j,k}$ 考虑到了 $1\sim j,2\sim j,\dots i-1\sim j$ 这些物品，而这些物品是不被包含在 $f_{j+1,k}$ 中的。那么，假设最优解是选取了若干个上述物品，又选取了 $i\sim j+1$ 这个物品，这种情况是考虑不到的。但我们发现，物品 $i\sim j+1$ 与前述物品的任意数量的组合都可以变成以下两种中的一种：

1. 若干个 $x \sim j$ 与若干个 $x\sim j+1$ 与若干个 $i \sim j$ 的组合，这是可以由 $f_{i,j}$ 以及 $f_{i,j-W}+V$​ 更新出来的。(其中的 $x$ 小于 $i$)
2. 若干个 $i \sim j+1$ 与若干个 $x\sim j+1$ 与若干个 $i \sim j$ 的组合，这是可以由 $f_{i+1,j}$ 以及 $f_{i,j-W}+V$ 更新出来的。(其中的 $x$ 小于 $i$)

你可以通过画图观察这些块的重合关系来发现这一点。这也是我们阅读出题者题解时最大的疑惑，在此略加解释。

代码

#include<bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
using namespace std;
const int N=2e3+5;
const int NN=2e6+5;
const int M=505;
ll f[N][M],ans[N],ansid[N];
int n,m;
ll w[N],v[N],wb[NN],vb[NN];
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&w[i],&v[i]);
        w[i]+=w[i-1];
        v[i]+=v[i-1];
        ansid[i]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=n;j>=i;j--){
            ll W=w[j]-w[i-1];
            ll V=v[j]-v[i-1];
            for(int k=W;k<=m;k++){
                f[j][k]=max({f[j][k],f[j+1][k],f[j][k-W]+V});
            }
        }
        for(int j=1;j<=m;j++){
            if(f[i][j]>ans[j]){
                ans[j]=f[i][j];
                ansid[j]=i;
            }
        }
    }
    for(int i=1;i<=m;i++) printf("%lld ",ans[i]);
    printf("\n");
    for(int i=1;i<=m;i++) printf("%lld ",ansid[i]);
    return 0;
}