题目大意：求解 0-1 背包前 K 优解的和。

题解：首先，可知对于状态 \(dp[j]\) 来说，能够转移到该状态的只有 \(dp[j],dp[j-w[i]]\)。对于 K 优解来说，只需对状态额外增加一个维度即可。接着，考虑状态转移的过程，即：需要从 \(dp[j][1...k]\rightarrow dp[j][1...k],dp[j-w[i]][1...k]\rightarrow dp[j][1...k]\)，可以考虑每次取出两堆数中的最大值进行比较，取较大的给当前状态，时间复杂度较高。可以发现，对于两个状态序列来说，\(dp[j][k-1]>dp[j][k]\) ，即：每个状态序列是单调递减的，可以考虑采用双指针遍历方法，时间复杂度较低。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=210;

const int maxv=5010;

inline int read(){

	int x=0,f=1;char ch;

	do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

	do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

	return f*x;

}

int n,m,K,dp[maxv][51],v[maxn],w[maxn];

int tmp[51];

void read_and_parse(){

	K=read(),m=read(),n=read();

	for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);

	memset(dp,0xcf,sizeof(dp));

	dp[0][1]=0;

}

void solve(){

	for(int i=1;i<=n;i++)

		for(int j=m;j>=w[i];j--){

			int x=1,y=1,tot=0;

			while(tot<=K){

				if(dp[j][x]>dp[j-w[i]][y]+v[i])tmp[++tot]=dp[j][x++];

				else tmp[++tot]=dp[j-w[i]][y++]+v[i];

			}

			for(int k=1;k<=K;k++)dp[j][k]=tmp[k];

		}

	long long ans=0;

	for(int i=1;i<=K;i++)ans+=dp[m][i];

	printf("%lld\n",ans);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}