记录编号	52017	评测结果	AAAAAAAAAAAA
题目名称	[USACO]总分	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.557 s
提交时间	2013-01-09 18:29:44	内存使用	0.28 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
class PROJECT{
public:
int p,t;//分数,时间
}s[10000];
bool cmp(PROJECT x,PROJECT y){
return x.t<y.t;
}
int main(){
freopen("inflate.in","r",stdin);
freopen("inflate.out","w",stdout);
int f[10001]={0};
int m,n;//时间和种类
scanf("%d%d",&m,&n);
int i,j,temp;
for(i=0;i<n;i++) scanf("%d%d",&s[i].p,&s[i].t);
sort(s,s+n,cmp);
for(i=1;i<=m;i++){
j=0;
f[i]=f[i-1];
while(i>=s[j].t&&j<n){
temp=f[i-s[j].t]+s[j].p;
if(temp>f[i]) f[i]=temp;
j++;
}
}
printf("%d\n",f[m]);
return 0;
}