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 <cstdio>
#include <cstring>
#include <algorithm>

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;
}