HDU 4278 卡特兰，区间DP

题意：每个人有一个DI值，现在有一个小黑屋，这些人的顺序可以利用这个小黑屋调整，调整方式是入栈出栈方式，也就是说，这里的方案是有卡特兰数个方式。

调整后使得 d1*0 + d2*1 + d3*2 + d4*3 ...... 最小。

分析：这个题目竟然会是区间DP。

考虑区间 [ L, R ] ，那么L，可以从任意位置出栈，枚举出栈位置，可以划分为两个部分，也就是说两个子问题，但是如何利用这两个子问题得到 d[L,R]，

d[L,R] = 前一部分 + D[L]*(i-L) + 后一部分 + 后一部分进位。

其中，后一部分的进位是一个前缀和*进多少位。

#include <bits/stdc++.h>

using namespace std;

const int maxn = ;

const int inf = 0x3f3f3f3f;

int a[maxn];

int d[maxn][maxn];

int su[maxn];

int dp(int L,int R) {

    if(L>=R) return ;

    if(d[L][R]!=-) return d[L][R];

    d[L][R] = inf;

    for(int i=L;i<=R;i++) {

        d[L][R] = min(d[L][R], dp(L+, i)+(i-L)*a[L]+dp(i+, R)+(su[R]-su[i])*(i+-L));

    }

    return d[L][R];

}

int main()

{

    //freopen("in.txt","r",stdin);

    int t;

    scanf("%d",&t);

    int kase = ;

    while(t--) {

        int n;

        scanf("%d",&n);

        memset(d,-,sizeof(d));

        memset(su,,sizeof(su));

        for(int i=;i<=n;i++) {

            scanf("%d",&a[i]);

            su[i] = su[i-] + a[i];     //前缀和

        }

        printf("Case #%d: %d\n",kase++,dp(,n));

    }

    return ;

}

巴特西

HDU 4278 卡特兰，区间DP

最新文章

热门文章