学步园

每年做一次完全背包，累加结果

#include<stdio.h>
#include<string.h>
int dp[1000000],w[11],v[11];
int sum,n,y;
int max(int a,int b){return a>b?a:b;}
void DP()
{
	int i,j,V=sum/1000;
	for(i=0;i<=V;i++) dp[i]=0;
	for(i=0;i<n;i++)
		for(j=w[i];j<=V;j++)
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		sum+=dp[V];
}
int main()
{
    int t,i;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&sum,&y);
		scanf("%d",&n);
		for(i=0;i<n;i++)  scanf("%d%d",&w[i],&v[i]),w[i]/=1000;
		while(y--)	DP();
		printf("%d\n",sum);
	}
	return 0;
}