滴，集训第二十一天打卡。
可能是对组队不太满意，都不大高兴做新的训练...
所以最近一直在磨DP，翻一下博客，发现最近都是DP啊...
这个石子合并的，我做的训练数据n是40000直线型的，一开始没注意，先做了环形，再换直线，然后发现朴素DP不能用了...
再看的GarsiaWachs算法，一上午啊，都在这了..
部分参考来自http://blog.csdn.net/acdreamers/article/details/18039073
石子合并有三种题型。
(1)有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（或最大）。
分析：当然这种情况是最简单的情况，合并的是任意两堆，直接贪心即可，每次选择最小的两堆合并。本问题实际上就是哈夫曼的变形。
(2)有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（或最大）。
分析：我们熟悉矩阵连乘，知道矩阵连乘也是每次合并相邻的两个矩阵，那么石子合并可以用矩阵连乘的方式来解决。
设dp[i][j]表示第i到第j堆石子合并的最优值，sum[i][j]表示第i到第j堆石子的总数量。那么就有状态转移公式：
最普通的算法O(n^3)：
其中，dp[i][j]代表i到j堆的最优值，sum[i]代表第1堆到第i堆的数目总和。
#include <stdio.h> #include <algorithm> using namespace std; int dp[205][205],sum[205],a[205]; int main() { int n,i,j,k,l,s; while(scanf("%d",&n)!=EOF) { s=0; for(i=1;i<=n;i++) { scanf("%d",&a[i]); s+=a[i]; sum[i]=s; } //memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) dp[i][i]=0; for(l=1;l<n;l++) { for(i=1;i<=n-l;i++) { j=i+l; dp[i][j]=1000000000; for(k=i;k<=j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); dp[i][j]+=sum[j]-sum[i-1]; } } printf("%d\n",dp[1][n]); } }
考虑四边形不等式优化，接近O(n^2)：
原状态转移方程中的k的枚举范围便可以从原来的(i~j-1)变为(s[i,j-1]~s[i+1,j])。
#include <stdio.h> #include <algorithm> using namespace std; int dp[105][105],sum[105],a[105],ss[105][105]; int main() { int n,i,j,k,l,s; while(scanf("%d",&n)!=EOF) { s=0; for(i=1;i<=n;i++) { scanf("%d",&a[i]); s+=a[i]; sum[i]=s; } //memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) dp[i][i]=0,ss[i][i]=i; for(l=1;l<n;l++) { for(i=1;i<=n-l;i++) { j=i+l; dp[i][j]=1000000000; for(k=ss[i][j-1];k<=ss[i+1][j];k++) { if(dp[i][j]>dp[i][k]+dp[k+1][j]) { dp[i][j]=dp[i][k]+dp[k+1][j]; ss[i][j]=k; } } dp[i][j]+=sum[j]-sum[i-1]; } } printf("%d\n",dp[1][n]); } }
在一个操场上摆放着一排N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。 试设计一个算法，计算出将N堆石子合并成一堆的最小得分。
Input
第一行是一个数N。 以下N行每行一个数A，表示石子数目。
Output
共一个数，即N堆石子合并成一堆的最小得分。
Sample Input
4
1
1
1
1
Sample Output
8
HINT
对于 100% 的数据，1≤N≤40000
对于 100% 的数据，1≤A≤200
思路：区间DP不能做了，范围40000开二维太大了。
#include <stdio.h> int stone[40005],ans,t; void combine(int k) { int tmp,i,j,d; tmp=stone[k-1]+stone[k]; ans+=tmp; t--; for(i=k;i<t;i++) stone[i]=stone[i+1]; for(j=k-1;stone[j-1]<tmp;j--) stone[j]=stone[j-1]; stone[j]=tmp; while(j>=2&&stone[j]>=stone[j-2]) { d=t-j; combine(j-1); j=t-d; } } int main() { int n,i,j; scanf("%d",&n); stone[0]=0x3f3f3f3f; stone[n+1]=0x3f3f3f3f-1; for(i=1;i<=n;i++) scanf("%d",&stone[i]); ans=0;t=3; for(i=3;i<=n+1;i++) { stone[t++]=stone[i]; while(stone[t-3]<=stone[t-1]) combine(t-2); } while(t>3) combine(t-1); printf("%d\n",ans); return 0; }
(3)问题(2)的是在石子排列是直线情况下的解法，如果把石子改为环形排列，又怎么做呢？
分析：状态转移方程为：
其中有：
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int dp[1005][1005]; int main() { int n,i,j,a[1001],sum[1005],s=0,k,l; scanf("%d",&n); sum[0]=0; for(i=1;i<=n;i++) { scanf("%d",&a[i]); s+=a[i]; sum[i]=s; } memset(dp,0,sizeof(dp)); for(l=2;l<=n;l++)//归并的石子长度 { for(i=1;i<=n-l+1;i++)//i为起点，j为终点 { j=i+l-1; dp[i][j]=1000000000; for(k=i;k<=j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); } } printf("%d\n",dp[1][n]); }
