Yiner的ACM

/**********************************
有一定的錢 存在銀行里
給出可存的錢數 和相應利息
第一年的利息會加入到第二年的本金中
***********************************/

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int d[50000],v[12],w[12];//數組開大了會超時
int main()
{

    int n;
    //freopen("out.txt","w",stdout);
    scanf("%d",&n);
    for(int l=1;l<=n;l++)
    {
        int c,k;
        int m;
        scanf("%d %d",&c,&k);
        scanf("%d",&m);

        for(int i=1;i<=m;i++)
        {
            scanf("%d %d",&v[i],&w[i]);
            v[i]/=1000;
        }
        while(k--)
        {
             int t=c/1000;//因為是1000的倍數 所以 都除以1000 優化一下子
        memset(d,0,sizeof(d));
        for(int i=1;i<=m;i++)
         for(int j=0;j<=t;j++)
         {   if(j>=v[i])
             if(d[j]<(d[j-v[i]]+w[i]))
            {
                d[j]=d[j-v[i]]+w[i];
            }
        }
         c=c+d[t];
        }
         printf("%d\n",c);
    }
    return 0;
}