hdu 4960 Another OCD Patient(記憶化)

hdu 4960 Another OCD Patient(記憶化)

題目鏈接：hdu 4960 Another OCD Patient

題目大意：給定一個長度為n的序列，然後再給出n個數ai,表示合成i個數的代價。每次可以將連續的子序列和成一個數，即為序列中各個項的和。要求將給定長度n的序列變成一個回文串，一個數字只能被合成一次。

解題思路：dp[l][r]表示從l到r被和成回文串的最小代價，dp[l][r]=min(val(r?l+1),val(r?i+1)+val(j?l+1)+dp[j+1][i?1]),當i每減少1，對應的j一定變大，這一點可以減少大部分的枚舉量。

#include 
#include 
#include 

using namespace std;
typedef long long ll;

const int maxn = 5005;

int N, arr[maxn], dp[maxn][maxn];
ll x, val[maxn];

inline ll getval (int l, int r) {
    return val[r] - val[l-1];
}

void init () {
    memset(dp, -1, sizeof(dp));

    val[0] = 0;
    for (int i = 1; i <= N; i++) {
        scanf("%I64d", &x);
        val[i] = val[i-1] + x;
    }

    for (int i = 1; i <= N; i++)
        scanf("%d", &arr[i]);
}

int solve (int l, int r) {

    if (l > r)
        return 0;

    if (dp[l][r] != -1)
        return dp[l][r];


    int& ret = dp[l][r];
    ret = arr[r-l+1];

    int mv = l;

    for (int i = r; i > l; i--) {
        ll u = getval(i, r);

        while (getval(l, mv) < u && mv < i)
            mv++;

        if (mv >= i)
            break;

        if (getval(l, mv) == u)
            ret = min(ret, arr[r-i+1] + arr[mv-l+1] + solve(mv+1, i-1));
    }
    return ret;
}

int main () {
    while (scanf("%d", &N) == 1 && N) {
        init();
        printf("%d\n", solve(1, N));
    }
    return 0;
}