2015年11月11日 星期三

2015/11/11 UVA 12991 - Game Rooms

/*
    看起來一臉DP樣 =ㄦ=

    DP[Ni][Nj][i]
    表示上一個第i項遊樂設施 
    出現在第Nj層樓
    且第Ni+1層樓 也有第i項遊樂設施

    注意邊界的狀況
    遞迴關係式 認真的想一下的話
    便會發現用 prefix sum
    可以O(1)更新
*/
/* https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=862&page=show_problem&problem=4874 */
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

int C[4001][2];
ll DP[4001][4000][2];
ll pre[4001][2];

int main()
{
    int T;
    scanf("%d", &T);

    for(int Ti = 1; Ti <= T; Ti++)
    {
        int N;
        scanf("%d", &N);

        for(int Ni = 1; Ni <= N; Ni++)
        {
            scanf("%d %d", &C[Ni][0], &C[Ni][1]);
            pre[Ni][0] = pre[Ni-1][0]+C[Ni][0];
            pre[Ni][1] = pre[Ni-1][1]+C[Ni][1];
        }

        DP[1][0][0] = C[1][0];
        DP[1][0][1] = C[1][1];

        for(int Ni = 2; Ni <= N; Ni++)
            for(int i = 0; i < 2; i++)
            {
                DP[Ni][0][i] = DP[Ni-1][0][i]+pre[Ni][i];
                DP[Ni][Ni-1][i] = DP[Ni-1][0][1-i];

                for(int Nj = 1; Nj < Ni-1; Nj++)
                {
                    int p = (Ni+Nj)/2;
                    DP[Ni][Nj][i] = DP[Ni-1][Nj][i]+pre[Ni][i]-pre[p][i];

                    DP[Ni][Ni-1][i] = min(DP[Ni][Ni-1][i], DP[Ni-1][Nj][1-i]);
                }

                DP[Ni][Ni-1][i] += C[Ni][i];
            }

        ll ans = (ll)1e18;

        for(int Nj = 1; Nj < N; Nj++)
            for(int i = 0; i < 2; i++)
            {
                int p = (N-Nj)/2;

                for(int pi = 0; pi < p; pi++)
                {
                    DP[N][Nj][i] -= (ll)(pi+1)*C[N-pi][i];
                    DP[N][Nj][i] += (ll)(N-Nj-pi)*C[N-pi][i];
                }

                ans = min(ans, DP[N][Nj][i]);
            }

        printf("Case #%d: %lld\n", Ti, ans);
    }
}

沒有留言:

張貼留言