题意：

买债券，总共n种债券，分别给出价格和收益，给出本金和年数，每年的本金都会改变，问最后本金加收益的和

要点：

很明显的完全背包问题，只要每次改变本金就可以，但这里有个问题就是数目过大，直接开数组会爆内存。题目中说本金和债券的价格都是1000的倍数，所以开数组时可以压缩，价格同时除1000就行，读题还是非常重要的。

15261964

Accepted

556K

79MS

627B

2016-03-13 11:54:41

#include
    
     #include
     
      #include
      
       #define max(a,b) a>b?a:bint dp[100000],value[15],interest[15];int main(){	int T,i,j;	scanf("%d", &T);	while (T--)	{		int start, year,n;		scanf("%d%d", &start, &year);		scanf("%d", &n);		for (i = 0; i < n; i++)		{			scanf("%d%d", &value[i], &interest[i]);			value[i] /= 1000;		//债券的价格同时也要除1000		}		int val = start;		while (year--)		{			memset(dp, 0, sizeof(dp));			start =val/1000;		//start是作为压缩后的dp下标			for (i = 0; i < n; i++)				for (j = value[i]; j <= start; j++)					dp[j] = max(dp[j], dp[j - value[i]] + interest[i]);			val += dp[start];		//收益和本金每年都要相加		}		printf("%d\n", val);	}	return 0;}