Another OCD Patient
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1757 Accepted Submission(s): 600
Problem Description
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.
Input
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.
Output
Sample Input
6 2 8 7 1
0 5 2 10 20
0
Sample Output
Hint
In 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.
Author
//2017-08-03
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm> using namespace std; const int N = ;
const int inf = 0x3f3f3f3f;
int n, a[N], dp[N][N];//dp[l][r]表示把区间l-r合并为回文的最小代价
long long v[N], sum[N]; int dfs(int l, int r){
if(l >= r)return dp[l][r] = ;
if(dp[l][r] != -)return dp[l][r];//记忆化搜索
int i = l;
dp[l][r] = v[r-l+];
for(int j = r; j >= l; j--){
while((sum[i]-sum[l-]) < (sum[r]-sum[j-]) && i < j){
i++;
}
if(j == i)break;
if((sum[i]-sum[l-]) == (sum[r]-sum[j-])){//划分子区间,需保证区间左端所有数之和与区间右端所有数之和相等。
int tmp = dfs(i+, j-)+v[i-l+]+v[r-j+];
dp[l][r] = dp[l][r] < tmp ? dp[l][r] : tmp;
}
}
return dp[l][r];
} int main(){
while(scanf("%d", &n)!=EOF && n){
sum[] = ;
for(int i = ; i <= n; i++){
scanf("%d", &a[i]);
sum[i] = sum[i-]+a[i];
}
for(int i = ; i <= n; i++)
scanf("%lld", &v[i]);
memset(dp, -, sizeof(dp));
int ans = dfs(, n);
printf("%d\n", ans);
} return ;
}