解题：洛谷 p1858 多人背包

题面

设$dp[i][j]$表示容量为$i$时的第$j$优解，因为是优解，肯定$dp[i][j]$是随着$j$增大不断递减的，这样的话对于一个新加进来的物品，它只可能从两个容量的转移的前$k$优解中转移过来，所以每次用两个指针扫一下转移过来就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5005,K=52;
int vol[N],val[N],tmp[K],dp[N][K];
int n,v,k,tot,p1,p2,ans;
int main ()
{
    scanf("%d%d%d",&k,&v,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&vol[i],&val[i]),tot+=vol[i];
    memset(dp,0xcf,sizeof dp),dp[0][1]=0;
    for(int i=1;i<=n;i++)
        for(int j=v;j>=vol[i];j--)
        {
            p1=p2=1;
            for(int h=1;h<=k;h++)
            {
                int c=(dp[j-vol[i]][p1]+val[i]>dp[j][p2]);
                tmp[h]=c?dp[j-vol[i]][p1++]+val[i]:dp[j][p2++];
            }
            for(int h=1;h<=k;h++) dp[j][h]=tmp[h];
        }
    for(int i=1;i<=k;i++) ans+=dp[v][i];
    printf("%d",ans);
    return 0;
}