Learning Vector

題目鏈接

題意：
n個向量，選k個首位相連，求與x軸的面積最大值分析：
首先明白：對於給定的一些向量，按照斜率從大到小排序的面積是最大的，那麼，對輸入的排序就是顯而易見的了
考慮當前的狀態，需要知道之前的高度才能表示當前狀態。顯然，對於高度相同的狀態還應該和已經用的向量數有關，所以狀態有兩個
轉移就是一個簡單的數學公式，沒什麼說的

const int maxn = 100;
struct Node
{
    int x, y;
    int operator< (const Node& rhs) const
    {
        return y * rhs.x > x * rhs.y;
    }
} ipt[60];

int dp[2][2600][60];

int main()
{
    int T, n, m;
    RI(T);
    FE(kase, 1, T)
    {
        REP(i, 2) REP(j, 2600) REP(k, 60) dp[i][j][k] = -100000000;

        RII(n, m);
        int maxh = 0;
        REP(i, n)
        {
            RII(ipt[i].x, ipt[i].y);
            maxh += ipt[i].y;
        }

        sort(ipt, ipt + n);
        int cur = 0;
        dp[cur][0][0] = 0;
        REP(i, n)
        {
            int x = ipt[i].x, y = ipt[i].y;
            cur ^= 1;
            FE(j, 0, maxh) FE(k, 0, m) dp[cur][j][k] = dp[cur ^ 1][j][k];
            FE(j, 0, maxh - y) FE(k, 0, m - 1)
                dp[cur][j + y][k + 1] = max(dp[cur][j + y][k + 1], dp[cur ^ 1][j][k] + j * x * 2 + x * y);
        }
        int ans = 0;
        FE(i, 0, maxh)
            ans = max(ans, dp[cur][i][m]);
        printf("Case %d: %d\n", kase, ans);
    }
    return 0;
}