110000 424000 4003000 250 Sample Output
14050 SourceNWERC2004 題意：給出初始資金，還有年數，然后給出每個物品的購買價格與每年獲得的利益，每個物品可選多次，要求在給出的年份后所能得到的最大本利之和。思路：由于給出的資金過大，循環會超時，題目說了本金與物品的購買價格都是1000的倍數，所以我們可以將他們都除以1000來進行壓縮，然后就是一道完全背包模板題了。代碼：
#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int N=20;const int M=500000;int dp[M];struct node{    int a,b;}str[N];int main(){    int T;    scanf("%d",&T);    while(T--)    {        int a,t;        scanf("%d%d",&a,&t);        int n;        scanf("%d",&n);        for(int i=0;i<n;i++)        {            scanf("%d%d",&str[i].a,&str[i].b);            str[i].a/=1000;        }        for(int i=1;i<=t;i++)        {            int ans=a/1000;            memset(dp,0,sizeof(dp));            for(int j=0;j<n;j++)                for(int k=str[j].a;k<=ans;k++)                    dp[k]=max(dp[k],dp[k-str[j].a]+str[j].b);            a+=dp[ans];        }        printf("%d/n",a);    }}