POJ 1738 - An old Stone Game

http://poj.org/problem?id=1738

There is an old stone game.At the beginning of the game the player picks n(1<=n<=50000) piles of stones in a line. The goal is to merge the stones in one pile observing the following rules:
At each step of the game,the player can merge two adjoining piles to a new pile.The score is the number of stones in the new pile.
You are to write a program to determine the minimum of the total score. 

Input

The input contains several test cases. The first line of each test case contains an integer n, denoting the number of piles. The following n integers describe the number of stones in each pile at the beginning of the game.
The last test case is followed by one zero. 

Output

For each test case output the answer on a single line.You may assume the answer will not exceed 1000000000.

Sample Input

1
100
3
3 4 3
4
1 1 1 1
0

Sample Output

0
17
8

https://www.fengiling.com/blog/view/?id=711857

有n堆石头排成一条直线 ，每堆石头的个数已知，现在要将这n堆石头合并成一堆，每次合并只能合并相邻的两堆石头，代价就是新合成石头堆的石头数，现在问将这n堆石头合并成一堆，最小代价是多少？

如果n的值较小，那么可以用dp[i][j]表示i-j堆合并成一堆的最小代价，那么dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j])

用区间DP做的代码

    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
            break;
        for(int i=1; i<=n; i++)
            for(int j=i; j<=n; j++)
                dp[i][j]=INF;
        sum[0]=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
            dp[i][i]=0;
        }

        if(n==1)
            printf("0
");
        else
        {
            for(int d=2; d<=n; d++)
            {
                for(int i=1; i<=n; i++)
                {
                    int s=i;
                    int e=i+d-1;
                    int add=sum[e]-sum[s-1];
                    for(int k=s; k<=e; k++)
                    {
                        dp[s][e]=min(dp[s][e],dp[s][k]+dp[k+1][e]+add);
                    }
                }
            }
            printf("%d
",dp[1][n]);
        }
    }

但是数据非常大，需要用GarsiaWachs算法，参考http://barty.ws/poj-1738-%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6%E7%9A%84garsiawachs%E7%AE%97%E6%B3%95/

石子合并问题的普遍做法是动态规划。dp[i][j]表示从i合并到j这段石子所需的最小代价和。从小到大枚举区间就行了，此时复杂度为O(N^3)。又因为有四边形不等式优化，设f[i][j]为区间[i,j]的最优分界点，则有f[i][j-1]<=f[i][j]<=f[i+1][j]，复杂度就降为O(N^2)。

此时对于N=50000的复杂度来说依然不可接受。Knuth在TAOCP里有一个很神奇的算法，叫做GarsiaWachs。具体算法如下：

step 0：初始数组为num[1..n]，num[0] = num[n+1] = INF

step 1：每次找到一个最小的i使得num[i-1]<=num[i+1]，将num[i-1]和num[i]合并为temp

step 2：找到前面一个最大的j使得num[j]>temp，将temp放在j之后。

step 3：重复1,2，直到剩余的堆数为1。

因为每次step2之后，指向的位置只需要向前一个即可(前面其他的都不会受到此次更新的影响)，因此每次指针的移动并不多。也因此，一个理论复杂度其实有O(N^2)的算法能够轻松过掉这道题。

https://www.cnblogs.com/lightspeedsmallson/p/4899584.html

还是石子归并问题，但是因为现在石子有50000堆，就需要开int[50000][50000]的数组，无论空间还是时间都可能挂掉，就得寻求更好的方法。

GarsiaWachs算法是从第一个石堆开始找符合stone[k-1]<stone[k+1]的石堆k，然后合并k-1与k堆，再向前找j堆石子，满足stone[j]>stone[k]+stone[k-1],插入到石堆j的后面。然后重新寻找。

我觉得GarsiaWachs算法的想法就是把石子就想象成是三堆，k-1 k k+1堆，如果stone[k-1]<stone[k+1]，那么一定是先合并k-1与k堆是合理的，之后把合并的堆插入到stone[j]的后面，是把stone[j+1]与stone[k-2]看成一个整体stone[m],所以现在就是stone[j],stone[m],(stone[k-1]+stone[k])，因为stone[k-1]+stone[k]<stone[j],所以插入到stone[j]后面是希望(stone[k-1]+stone[k])与stone[m]先合并，这样就不断地都是最优解，得到的结果也就是最优结果。

http://www.aichengxu.com/suanfa/10961063.htm

石子合并问题升级版（因为n<=5W）
不得不先吐槽一下，我只是搜了一下POJ简单石子合并问题，然后就开心的去写1738了，然后感觉n好大呀，结果一看Source男人八题，QAQ，度娘太坑人了QAQing
分析：
因为n<=5W，开个dp数组根本开不下，所以我们要学习一种萌萌哒的算法——GarsiaWachs算法
我们先从最简单的看起，n=3时：
ans1=（a+b）+（（a+b）+c）
ans2=（b+c）+（（b+c）+a）
假设ans1<=ans2，==>a<=c
GarsiaWachs算法便是基于这种性质，每一次都在当前石子中找到最小的num[i-1]<=num[i+1]，然后将num[i-1]和num[i]合并为sum，然后从右往左找第一个num[j]大于等于sum的j，把sum插入到j的后面…………有个问题？？这样做不会违背只能合并相邻石子的性质吗？？Of course不会我们可以num[j+1]~num[i-2]看做一个num[mid]的整体，因为num[j]>=num[i-1]+num[i]所以我们一定是先合并sum，所以把sum放在num[mid]前面还是后面都没有关系啦
by >o< neighthorn

https://www.fengiling.com/blog/view/?id=711857