学步园

参考：http://hi.baidu.com/lewutian/blog/item/6c4401efc84a1ce2ce1b3e94.html

题目大意：给你一笔钱，然后给你一个年限，还有每买一份债券，到年底能得到多少利息，要你求过了这个年限后，本金加利息的最大值。

每年的年末可以利用上一年得到的本金加利息的钱重新分配一次债券

解题思路：典型的完全背包问题，每种债券可以买多份>=0，只要不超过本金。

因为每买的债券值不低于1000，所以可以把每次的总值除以1000，还有债券值除以1000,这样的空间就缩小到0~~~1000中了，而每次得的利息小于1000的不能去买债券，所以能这样优化。这样可以缩短很多时间

注意在循环每年更新dp时，还是手动用循环给dp赋初值0,我用memset(dp,0,sizeof(dp));就超时了，因为每次循环是给整个dp赋值

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 2001000;
int n, d, total, year, p[11], v[11], dp[maxn];;
int main()
{
   
    scanf("%d", &n);
    while(n-- != 0)
    {
        scanf("%d %d", &total, &year);
        scanf("%d", &d);
        for(int i = 0; i < d; i++)
        {
            scanf("%d %d", &p[i], &v[i]);
            p[i] /= 1000;
        }
        for(int i = 0; i < year; i++)
        {
            int tmp = total / 1000;
            for(int k = 0; k <= tmp; k++)
                dp[k] = 0;
            for(int k = 0; k < d; k++)
            {
                for(int val = p[k]; val <= tmp; val++)
                    dp[val] = max(dp[val], dp[val - p[k]] + v[k]);
            }
            total += dp[tmp];
        }
        printf("%d\n", total);
    }
    
    return 0;
}