两种石子归并_牛客博客

其实dp是我非常喜欢的一个东西，因为他的代码短小精炼。。。。

题目描述 Description

有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。

输入描述 Input Description

第一行一个整数n（n<=100）

第二行n个整数w1,w2...wn (wi <= 100)

输出描述 Output Description

一个整数表示最小合并代价

样例输入 Sample Input

4

4 1 1 4

样例输出 Sample Output

18

首先我们先说比较简单的石子归并的版本——区间dp。

上面这道题可以说是区间dp的最经典的例题了，然而到今天我才真正的看明白这个题答案的真正意义。

首先我们很容易想到贪心的思路，就是每次将最小的两组和并，然而事实上是不可以的，利用贪心的是与这个题类似的合并果子，这两个题的区别就在于，此题必须是相邻的两组合并。这会导致什么，最小的两组不一定相邻，然后如果贪心就gg了。

那么说正解，我们可以将将这个数组看作一个区间，然后对这个区间进行划分，即将划分处进行合并，然后枚举划分的点，再对划分的点进行划分，取最优的划分点。区间成为两个时就别无选择。

怎么说出了递归搜索的感觉？没错，当时学长将这道题的时候，我的思路就是记忆化搜索，然而学长想讲的是递推。但我确实用记忆化搜索写出来了。

那么递推怎么写？

我们可以枚举区间左端点，再枚举区间长度，这样区间的左端点和右端点就都有了，然后再枚举划分点，取出不同划分点中的最大值。这样就完成了递推，

具体一点的看一下代码就懂了。

PS：昨天了解到，所有的记忆化搜索都可以写出递推式，但是记忆化搜索往往更好想。

附上代码

 1 #include<iostream>
 2 #include<cstring> 
 3 #include<cstdio>
 4 using namespace std;
 5 int n,f[110][110],a[110],sum[110];
 6 int ff(int x,int y)
 7 {
 8     if(x==y) return f[x][y]=0;
 9     if(f[x][y]) return f[x][y];
10     if(x==y-1) return f[x][y]=sum[y]-sum[x-1];
11     f[x][y]=0x6fffff;
12     for(int i=x;i<=y;++i)
13     f[x][y]=min(f[x][y],ff(x,i)
14     +ff(i+1,y)+sum[y]-sum[x-1]);
15     return f[x][y];    
16 }
17 int main()
18 {
19     scanf("%d",&n);
20     for(int i=1;i<=n;++i)
21     {
22         scanf("%d",&a[i]);
23         sum[i]=a[i]+sum[i-1];
24     }
25     cout<<ff(1,n);
26     return 0;
27 }

记忆化搜索

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 int a[110],n,sum[110],f[110][110];
 6 int main()
 7 {
 8     scanf("%d",&n);
 9     for(int i=1;i<=n;++i)
10     {
11         scanf("%d",&a[i]);
12         sum[i]=sum[i-1]+a[i];
13     }
14     for(int i=1;i<=n;++i)
15     {
16         for(int l=1,r=l+i;l+i<=n;++l,++r)
17         {
18             f[l][r]=0x7fffff;
19             for(int j=l;j<=r;++j)
20             {
21                 
22                 f[l][r]=min(f[l][r],f[l][j]+f[j+1][r]+sum[r]-sum[l-1]);
23             }
24         }
25     }
26     printf("%d",f[1][n]);
27     return 0;
28  }

递推

然后就进阶了

题目描述

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

输入输出格式

输入格式：

数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

输出格式：

输出共2行,第1行为最小得分,第2行为最大得分.

输入输出样例
输入样例#1：
4
4 5 9 4
输出样例#1：
43
54

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int N=110;
 5 int f[N*2][N*2],a[N*2],n,ff[N*2][N*2],sum[N*2];
 6 int main()
 7 {
 8   scanf("%d",&n);
 9   for(int i=1;i<=n;++i)
10   {
11     scanf("%d",&a[i]);
12     a[i+n]=a[i];
13   }
14   for(int i=1;i<=n*2;++i)
15   {
16     sum[i]=sum[i-1]+a[i];
17   }
18   for(int i=1;i<=n*2;++i)
19     for(int j=1;j<=n*2;++j)
20       {
21         if(i==j) continue;
22         f[i][j]=-0x7ffffff;
23         ff[i][j]=0x7ffffff;
24       }
25   for(int len=2;len<=n;++len)
26   {
27     for(int l=1;l<=n*2;++l)
28     {
29       int r=l+len-1;
30       if(r>n*2) break;
31       for(int k=l;k<r;++k)
32       {
33         f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
34         ff[l][r]=min(ff[l][r],ff[l][k]+ff[k+1][r]+sum[r]-sum[l-1]);
35       }
36     }
37   }
38 /*  for(int i=1;i<=n*2;++i)
39   {
40     for(int j=i;j<=n*2;++j)
41     {
42       printf("%d %d %d\n",i,j,f[i][j]);
43     }
44   }*/
45   int ansmin=0x7fffff,ansmax=-0x7ffffff;
46   for(int i=1;i<=n;++i)
47   {
48     ansmin=min(ansmin,ff[i][i+n-1]);
49     ansmax=max(ansmax,f[i][i+n-1]);
50   }
51   printf("%d\n%d",ansmin,ansmax);
52   return 0;
53 }

石子归并环形