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

题目描述  <small>Description</small>

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

输入描述  <small>Input Description</small>

第一行一个整数n(n<=100)

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

输出描述  <small>Output Description</small>

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

样例输入  <small>Sample Input</small>

4

4 1 1 4

样例输出  <small>Sample Output</small>

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 }
石子归并环形