九度教程第101题

题目地址：http://jobdu.sinaapp.com/problem.php?cid=1040&pid=100

提供组数据：

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语言源码：

#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]);elsedp[i][j]=dp[i-1][j];}}printf("%d\n",dp[n][t]);}}