题意：
给出n组x，y增量，从（0,0）开始以x,y坐标增加后等到的终点坐标，可以构成一个面积，再以这个终点为起点再增加，以此类推，使用增量顺序不同，得到的面积不，求用k组增量能得到的最大的面积。
分析：
先按(x,y)和（0,0）确定的斜率降序排列（这个贪心好想）dp[j][k]表示用j组增量能达到右边界的高度为k
时得到的最大的面积。dp[k+1][j+p[i].y]=max(dp[k+1][j+p[i].y],dp[k][j]+(2*j+p[i].y)*p[i].x);
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <complex> #include <cassert> #include <utility> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; typedef pair<int,int> PII; typedef long long ll; #define lson l,m,rt<<1 #define pi acos(-1.0) #define rson m+1,r,rt<<11 #define All 1,N,1 #define N 55 #define M 2501 #define INF 1e10 #define read freopen("in.txt", "r", stdin) const ll INFll = 0x3f3f3f3f3f3f3f3fLL; const int mod = 1000000007; struct point{ int x,y; double k; }p[N]; int dp[N][N*N],n,q; bool cmp(point a,point b) { return a.k>b.k; } int solve(){ sort(p,p+n,cmp); memset(dp,-1,sizeof(dp)); dp[0][0]=0; for(int i=0;i<n;++i) for(int j=M;j>=0;--j){ for(int k=q-1;k>=0;--k){ if(dp[k][j]>=0) dp[k+1][j+p[i].y]=max(dp[k+1][j+p[i].y],dp[k][j]+(2*j+p[i].y)*p[i].x); } } int maxv=-1; for(int i=0;i<=M;++i) maxv=max(maxv,dp[q][i]); return maxv; } int main() { int t,ca=0; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&q); for(int i=0;i<n;++i){ scanf("%d%d",&p[i].x,&p[i].y); if(p[i].x==0)p[i].k=INF; else p[i].k=1.0*p[i].y/p[i].x; } printf("Case %d: %d\n",++ca,solve()); } return 0; }
原文：http://www.cnblogs.com/zsf123/p/4909648.html