首页 > 代码库 > hdu 4960 记忆化搜索 DP

hdu 4960 记忆化搜索 DP

2024-07-18 13:53:34   225人阅读

Another OCD Patient

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 490    Accepted Submission(s): 180

Problem Description
   Xiaoji is an OCD (obsessive-compulsive disorder) patient. This morning, his children played with plasticene. They broke the plasticene into N pieces, and put them in a line. Each piece has a volume Vi. Since Xiaoji is an OCD patient, he can‘t stand with the 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.
 
Input
   The input contains multiple test cases.
   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
   Output one line containing the minimum cost of all operations Xiaoji needs.
 
Sample Input
56 2 8 7 10 5 2 10 200
 
Sample Output
10
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
SYSU
 
Source
2014 Multi-University Training Contest 9
 
Recommend
We have carefully selected several similar problems for you:  4970 4968 4967 4966 4964 
 
记忆化搜索，由于每个碎片值都是正数，所以每个前缀和后缀都是递增的，就可以利用twopointer去找到每个相等的位置，然后下一个区间相当于一个子问题，用记忆化搜索即可，复杂度接近O(n^2)
 
转自 ：http://blog.csdn.net/accelerator_/article/details/38690595

 

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 10 #define N 500511 #define M 1512 #define mod 613 #define mod2 10000000014 #define ll long long15 #define maxi(a,b) (a)>(b)? (a) : (b)16 #define mini(a,b) (a)<(b)? (a) : (b)17 18 using namespace std;19 20 int n;21 ll v[N],sum[N];22 int a[N],dp[N][N];23 24 int DP(int l,int r)25 {26     //int i;27     //ll s1,s2;28     if(dp[l][r]!=-1) return dp[l][r];29     dp[l][r]=a[r-l+1];30     if(l>=r) return dp[l][r]=0;31     32     //i=l;33     int now=l;34     ll re;35     for(int i=r;i>=l;i--){36         re=sum[r]-sum[i-1];37         while(sum[now]-sum[l-1]<re && now<i)38             now++;39         if(now==i) break;40         if(sum[now]-sum[l-1]==re){41             dp[l][r]=min(dp[l][r],DP(now+1,i-1)+a[now-l+1]+a[r-i+1]);42         }43     }44     return dp[l][r];45 }46 47 int main()48 {49     int i;50     //freopen("data.in","r",stdin);51     //scanf("%d",&T);52     //for(int cnt=1;cnt<=T;cnt++)53     //while(T--)54     while(scanf("%d",&n)!=EOF)55     {56         if(n==0) break;57         memset(dp,-1,sizeof(dp));58         //memset(sum,0,sizeof(sum));59         for(i=1;i<=n;i++){60             scanf("%I64d",&v[i]);61             sum[i]=sum[i-1]+v[i];62         }63         for(i=1;i<=n;i++){64             scanf("%d",&a[i]);65         }66         DP(1,n);67         printf("%d\n",dp[1][n]);68     }69 70     return 0;71 }

 


联系
我们