建设国家

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1475

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#define MAX 1000+5
int n,h,dp[MAX][MAX]; 
struct city{
	int hi;
	int pi;
}c[MAX];
int cmp(city x,city y ){
	if(x.hi==y.hi){
		return x.pi>y.pi;
	}else return x.hi>y.hi;//降序 
}
int main(){
	//freopen("yzhid.in","r",stdin);
	scanf("%d %d",&n,&h);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&c[i].hi,&c[i].pi);
	sort(c+1,c+1+n,cmp);
	dp[0][0]=0;
	int tmax=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++){
			dp[i][j]=dp[i-1][j];
			if(j+c[i].hi<=h && dp[i-1][j-1]+c[i].pi>dp[i][j] ){
				dp[i][j]=dp[i-1][j-1]+c[i].pi;
				tmax=max(tmax,dp[i][j]+c[i+1].pi);
			}
		}
	printf("%d",tmax);
	return 0;
}