题意：从n个男孩中挑出k个，每个人有两个属性u，v
怎样挑选能得到最大的value
定义状态：dp[ i ][ j ]:从前i个中挑出j个得到的最大value
对于第i个，若选择,dp[i][j]=dp[i-1][j-1]+a[i].u-a[i].v*(j-1)
若不选择，dp[i][j]=dp[i-1][j]+0;
View Code
1 #include<algorithm> 2 #include<stdlib.h> 3 #include<string.h> 4 #include<stdio.h> 5 using namespace std; 6 const int maxn = 1005; 7 struct node{ 8 int u,v; 9 }a[ maxn ]; 10 int cmp( node a,node b ){ 11 return a.v>b.v; 12 } 13 int dp[ maxn ][ maxn ];// 14 ////dp[i][j]:从前i个中挑出j个得到的最大值 15 ////dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+u-v*(j-1)) 16 int main(){ 17 int n,k; 18 while( scanf("%d%d",&n,&k)==2 ){ 19 for( int i=1;i<=n;i++ ) 20 scanf("%d",&a[ i ].u); 21 for( int i=1;i<=n;i++ ) 22 scanf("%d",&a[ i ].v); 23 sort( a+1,a+n+1,cmp ); 24 memset( dp,0,sizeof(dp) ); 25 for( int i=1;i<=n;i++ ){ 26 for( int j=1;j<=k;j++ ){ 27 if( i-1<=j-1 ){ 28 dp[i][j]=dp[i-1][j-1]+a[i].u-(j-1)*a[i].v; 29 } 30 else{ 31 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+a[i].u-(j-1)*a[i].v); 32 } 33 } 34 } 35 printf("%d\n",dp[n][k]); 36 } 37 return 0; 38 }