九度教程第101題

提供組數據： input： 105 10 12 11 16 16 24 15 7 9 29 24 32 25 5 3 43 32 31 41 1 7 output： 112 C語言源碼： [cpp]   #include<stdio.h>   int dp[101][1001];   typedef struct grass   {       int time;       int worth;   }grass;   grass g[101];   int max(int a,int b)   {       return a>b?a:b;   }   int main()   {       int t,n,i,j;       while(scanf("%d %d",&t,&n)!=EOF)       {           for(i=1;i<=n;i++)               scanf("%d %d",&g[i].time,&g[i].worth);           for(i=0;i<=n;i++)               for(j=0;j<=t;j++)                   dp[i][j]=0;           for(i=1;i<=n;i++)           {               for(j=0;j<=t;j++)               {                   if(g[i].time<=j)                       dp[i][j]=max(dp[i-1][j-g[i].time]+g[i].worth,dp[i-1][j]);                   else                       dp[i][j]=dp[i-1][j];               }           }           printf("%d\n",dp[n][t]);       }   }