UVALive 6208

离散DP

由于状态转移需要记录三维，第三维是之前的高度，而这个变量取值只有离散的几个，故用map来存。

不过一开始一直T啊，最后加些剪枝终于过了。。。

[cpp]
#include
#include
#include
#include
#include
#include

#include
#include
#include
#include
#include
#include

bool cmp(struct Point a,struct Point b){
return a.y*b.x > a.x*b.y;
}

map dp[60][60];

int main(){
int t,T,n,kk,i,j,k;
scanf("%d",&T);
for(t=1;t<=T;t++){
scanf("%d %d",&n,&kk);
for(i=1;i<=n;i++) scanf("%d %d",&point[i].x,&point[i].y);
sort(point+1,point+n+1,cmp);
for(i=1;i<=n;i++)
for(j=1;j<=kk;j++) dp[i][j].clear();
for(i=0;i<=n;i++)
dp[i][0][0]=0;
//for(i=1;i<=n;i++) printf("***%d %d\n",point[i].x,point[i].y);
int t1,t2;
for(i=1;i<=n;i++){
for(j=1;j<=i && j<=kk;j++){
if(j+n-i t1=0;t2=0;
dp[i][j]=dp[i-1][j];
for(map::iterator k=dp[i-1][j-1].begin();k!=dp[i-1][j-1].end();k++){
if(k->first+point[i].ysecond+(k->first*2+point[i].y)*point[i].x t1=k->first+point[i].y;
t2=k->second+(k->first*2+point[i].y)*point[i].x;
}
for(map::iterator k=dp[i-1][j-1].begin();k!=dp[i-1][j-1].end();k++){
if(k->first+point[i].ysecond+(k->first*2+point[i].y)*point[i].x dp[i][j][k->first+point[i].y]=max(dp[i][j][k->first+point[i].y],k->second+(k->first*2+point[i].y)*point[i].x);
}
}
}
int ans=0;
for(i=1;i<=n;i++){
for(map::iterator k=dp[i][kk].begin();k!=dp[i][kk].end();k++){
ans=max(ans,k->second);
}
}
printf("Case %d: %d\n",t,ans);
}
return 0;
}