離散DP
由於狀態轉移需要記錄三維，第三維是之前的高度，而這個變量取值只有離散的幾個，故用map來存。
不過一開始一直T啊，最後加些剪枝終於過了。。。
[cpp]
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int inf =((~(0U))>>1);
struct Point{
int x,y;
}point[100];
bool cmp(struct Point a,struct Point b){
return a.y*b.x > a.x*b.y;
}
map<int,int> 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<kk)continue;
t1=0;t2=0;
dp[i][j]=dp[i-1][j];
for(map<int,int>::iterator k=dp[i-1][j-1].begin();k!=dp[i-1][j-1].end();k++){
if(k->first+point[i].y<t1 && k->second+(k->first*2+point[i].y)*point[i].x<t2) continue;
t1=k->first+point[i].y;
t2=k->second+(k->first*2+point[i].y)*point[i].x;
}
for(map<int,int>::iterator k=dp[i-1][j-1].begin();k!=dp[i-1][j-1].end();k++){
if(k->first+point[i].y<t1 && k->second+(k->first*2+point[i].y)*point[i].x<t2) continue;
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<int,int>::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;
}
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int inf =((~(0U))>>1);
struct Point{
int x,y;
}point[100];
bool cmp(struct Point a,struct Point b){
return a.y*b.x > a.x*b.y;
}
map<int,int> 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<kk)continue;
t1=0;t2=0;
dp[i][j]=dp[i-1][j];
for(map<int,int>::iterator k=dp[i-1][j-1].begin();k!=dp[i-1][j-1].end();k++){
if(k->first+point[i].y<t1 && k->second+(k->first*2+point[i].y)*point[i].x<t2) continue;
t1=k->first+point[i].y;
t2=k->second+(k->first*2+point[i].y)*point[i].x;
}
for(map<int,int>::iterator k=dp[i-1][j-1].begin();k!=dp[i-1][j-1].end();k++){
if(k->first+point[i].y<t1 && k->second+(k->first*2+point[i].y)*point[i].x<t2) continue;
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<int,int>::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;
}
