九度教程第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]);
}
}
补充：软件开发 , C++ ,
