首页 > 代码库 > 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 <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;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。