Another OCD Patient
Time Limit: 2000/1000 MS (Java/Others) Memory Limit:
131072/131072 K (Java/Others)
disorder of the volume of the N pieces of plasticene. Now he wants to merge some successive pieces so that the volume in line is symmetrical! For example, (10, 20, 20, 10), (4,1,4) and (2) are symmetrical but (3,1,2), (3, 1, 1) and (1, 2, 1, 2) are not.
However, because Xiaoji's OCD is more and more serious, now he has a strange opinion that merging i successive pieces into one will cost ai. And he wants to achieve his goal with minimum cost. Can you help him?
By the way, if one piece is merged by Xiaoji, he would not use it to merge again. Don't ask why. You should know Xiaoji has an OCD.
The first line of each case is an integer N (0 < N <= 5000), indicating the number of pieces in a line. The second line contains N integers Vi, volume of each piece (0 < Vi <=10^9). The third line contains N integers ai (0 < ai <=10000), and
a1 is always 0.
The input is terminated by N = 0.
5 6 2 8 7 1 0 5 2 10 20 0
10HintIn the sample, there is two ways to achieve Xiaoji's goal. [6 2 8 7 1] -> [8 8 7 1] -> [8 8 8] will cost 5 + 5 = 10. [6 2 8 7 1] -> [24] will cost 20.
分析：由于题目要求把原数列变成回文数列，所以只需要找出原数组中的关键点，然后利用这些关键点进行dp。
所谓的关键点就是指数对（i，j）满足v1+v2+……+vi = vj+……+vn。因为关键点i和j是一一对应的，所以一维dp就能解决问题。
dp[i]表示添加第i个关键点后形成回文数列的最小花费
则dp[i] = min(dp[j-1]+a[l_num[j,i]]+a[r_num[j,i]]|1<=j<=i),其中l_num[j,i]表示左边第j个关键点到第i个关键点的元素个数的总数，r_num[j,i]表示右边第j个关键点到第i个关键点的元素个数的总数
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 0x3fffffff
const int N = 5005;
int n, v[N], a[N];
int dp[N];
int L[N], R[N], num; //L[]和R[]记录关键点
void Init()
{
num = 0;
int l = 1, r = n, l_num = 1, r_num = 1;
int l_val = v[1], r_val = v[n];
while(l < r) {
if(l_val < r_val) {
l_val += v[++l];
l_num++;
}
else if(l_val > r_val) {
r_val += v[--r];
r_num++;
}
else {
L[++num] = l_num;
R[num] = r_num;
l_num = r_num = 1;
l_val = v[++l];
r_val = v[--r];
}
}
}
int main()
{
while(~scanf("%d",&n) && n) {
for(int i = 1; i <= n; ++i) scanf("%d",&v[i]);
for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);
Init();
for(int i = 1; i <= num; i++) {
int num1 = 0, num2 = 0;
dp[i] = INF;
for(int j = i; j >= 1; --j) {
num1 += L[j];
num2 += R[j];
dp[i] = min(dp[i], dp[j-1] + a[num1] + a[num2]);
}
}
int ans = a[n], cnt = n;
for(int i = 1; i <= num; ++i) {
cnt -= L[i] + R[i];
ans = min(ans, dp[i] + a[cnt]);
}
printf("%d\n", ans);
}
return 0;
}