UVa 12589 Learning Vector

제목: n개의 벡터(0<=x, y<=50)가 있는데, 선택한 K개(n, k<=50)의 면적은 최대 얼마입니까?
사고방식: 먼저 한 가지를 확정하고 선택한 k개의 벡터에 대해 사율에 따라 큰 것부터 작은 것까지 순서대로 배치하고 면적이 가장 크다.(그렇지 않으면 몇 개의 평행 사각형의 면적을 손실할 수 있다) 그리고 DP, DP[id][cur][height]는 각각 전 id의 벡터를 나타낸다. 이미cur의 벡터를 선택했고 높이는 height의 최대 면적이다.면적 계산 공식은 x0*y0+2*x1*y0+x1*y1+2*x2*(y0+y1)......기억화 검색으로 초기화 최적화 주의!

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 50+10;
const int INF = 1e9;
int dp[maxn][maxn][2600];
int vis[maxn][maxn][2600];
struct Vector{
    int x,y;
    Vector(int x = -1,int y = -1):x(x),y(y){}
    friend bool operator < (Vector a,Vector b) {
        return a.y*b.x > a.x*b.y;
    }
};
Vector V[maxn];
int n,k;
int plu;
int ans;
int dfs(int id,int cur,int hi) {
    if(cur==k) return 0;
    if(id==n) return -INF;
    if(vis[id][cur][hi] == plu) return dp[id][cur][hi];
    vis[id][cur][hi] = plu;
    int ans = 0;
    if(ans < dfs(id+1,cur,hi)) ans = dfs(id+1,cur,hi);
    if(ans < dfs(id+1,cur+1,hi+V[id].y)+2*V[id].x*hi+V[id].x*V[id].y) ans = dfs(id+1,cur+1,hi+V[id].y)+2*V[id].x*hi+V[id].x*V[id].y;
    return dp[id][cur][hi] = ans;
}
void input() {
    ans = 0;
    scanf("%d%d",&n,&k);
    int sum = 0;
    for(int i = 0; i < n; i++) {
        scanf("%d%d",&V[i].x,&V[i].y);
        sum += V[i].y;
    }
    sort(V,V+n);
}
void solve() {
    plu++;
    ans = dfs(0,0,0);
    printf("%d
",ans);
}
int main() {

    int ncase,T=1;
    cin >> ncase;
    memset(vis,0,sizeof vis);
    plu = 1;
    while(ncase--) {
        input();
        printf("Case %d: ",T++);
        solve();
    }
    return 0;
}