wikioi 1048 石子归并

http://www.voidcn.com/article/p-ybexlmby-wd.html

有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

https://blog.csdn.net/fuyukai/article/details/43793863
区间型动态规划是我个人感觉动态规划类型里面最好理解的一种

拿到题目的时候，我首先想到的是“合并果子”那道题，做法大概是建堆+贪心，可是仔细看一下，两道题目却有很大不同，这道题合并的时候需要两石子相邻，明显贪心已经做不了了，所以我们用动规来试试看。区间型的动规，就是与区间有关的DP，我们需要考虑区间的一些特点来解决：
不妨用dp[i][j]表示合并 i 到 j 这一区间的石子所产生的消耗，那我们最终的结果就是dp[1][n]，我们怎么才能得到最重的dp[1][n]呢？
状态转移方程是：dp[i][j]=min(dp[i][j] , dp[i][k] + dp[k+1][j] + sum[i:j])
我们需要从两个石子开始合并，最终变成 n 个石子开始合并，代码如下：

for(int len=2;len<=n;len++)
{
    for (int i=1;i<=n-len+1;i++)
    {
        int j=i+len-1;
        for (int k=i;k<j;k++)
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
    }
}
1
2
3
4
5
6
7
8
9
我们事先需要预处理一下，获得sum数组（省去了一个二重循环）：

for (int i=1;i<=n;i++)
    sum[i]=sum[i-1]+a[i];

https://www.cnblogs.com/qscqesze/p/4010949.html

dp[i][j]=min(dp[i][j],dp[i][k],dp[k+1][j]+sum[i][j]);

表示i-j的最小合并代价。

13     int getMinval(int a[],int n)  
14     {  
15         for(int i=0;i<n;i++)  
16             dp[i][i] = 0;  
17         for(int v=1;v<n;v++)  
18         {  
19             for(int i=0;i<n-v;i++)  
20             {  
21                 int j = i + v;  
22                 dp[i][j] = INF;  
23                 int tmp = sum[j] - (i > 0 ? sum[i-1]:0);  
24                 for(int k=i;k<j;k++)  
25                     dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j] + tmp);  
26             }  
27         }  
28         return dp[0][n-1];  
29     }  
30       
31     int main()  
32     {  
33         int n;  
34         while(scanf("%d",&n)!=EOF)  
35         {  
36             for(int i=0;i<n;i++)  
37                 scanf("%d",&a[i]);  
38             sum[0] = a[0];  
39             for(int i=1;i<n;i++)  
40                 sum[i] = sum[i-1] + a[i];  
41             printf("%d\n",getMinval(a,n));  
42         }  
43         return 0;  
44     }  

http://www.voidcn.com/article/p-ybexlmby-wd.html

题意：给出n个数，相邻两数可以合并，合并的代价是两数之和，问合并成一个数的最小代价。

分析：典型的区间dp，用dp[i][j]记录[i,j]区间合并为一个数的最小代价，那么递推方程：dp[i][j] = min(dp[i][k]+dp[k][j])+sum[i][j]，其中i<k<j，sum[i][j]为[i,j]区间的和，也就是本次合并的代价。先从i-j=1开始遍历，逐步增大[i,j]区间的长度，最终dp[0][n-1]即为结果

ps：注意边界，如dp[i][i] = 0, sum[i][i] = a[i]，a[i]就是第i个数的值

    int n;
    cin>>n;
    memset(sum,0,sizeof(sum));
    for(int i=0; i<n; i++)
    {
        cin>>sum[i][i];
        for(int j=0; j<i; j++)
            sum[j][i] = sum[j][i-1]+sum[i][i];
    }
    memset(dp,0,sizeof(dp));
    for(int k=1;k<n;k++)
    {
        for(int i=0; i+k<n; i++)
        {
            int minn = -1;
            for(int j=i;j<i+k;j++)
            {
                if(minn<0 || dp[i][j]+dp[j+1][i+k] < minn)
                    minn = dp[i][j]+dp[j+1][i+k];
            }
            dp[i][i+k] = minn + sum[i][i+k];
        }
    }
    cout<<dp[0][n-1]<<endl;

https://blog.csdn.net/kingzone_2008/article/details/12361327

sum[i[用于记录从第1堆到第i堆（包含i）石子的总重量。

dp[i][j]表示从第i堆（包含i）到第j堆（包含j）石子的合并的最小代价。

状态转移方程为：dp[i][j] = minimize{dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]}, k从i到j（不包含j）。

len=2表示第一次合并的情况，此时合并的石子为2堆。此时，i从1到n-len+1，j=i+len-1。


Different
https://dannyyo.iteye.com/blog/2172612
GarsiaWachs算法

11079 可以移动的石子合并（必做）

有n堆石子形成一行(a1,a2,…,an，ai为第i堆石子个数)，现要将石子合并成一堆，规定每次可选择至少2堆最多k堆移出然后合并，每次合并的分值为新堆的石子数。
若干次合并后，石子最后肯定被合并为一堆，得分为每次合并的分值之和。
现在求解将这n堆石子合并成一堆的最低得分和最高得分。

输入格式

两行。第一行n和k，第二行a1 a2 … an，每个ai(1<=i<=n)表示第i堆石子的个数，n<=100，2<=k<=n。

输出格式

仅一行，为石子合并的最低得分和最高得分，中间空格相连。

输入样例

7 3
45 13 12 16 9 5 22

输出样例

199 593

提示

此题贪心算法求解.
给这题标记标签"dp"方法是同学所为,并非老师标注.动规不是不可以,但有更好更快的贪心解法的.

如7堆石头，每次可选择最少2堆最多3堆合并，可以如下这样合并：
第1次合并：45+22=67
第2次合并：67+16=83
第3次合并：83+13=96
第4次合并：96+12=108
第5次合并：108+9=117
第6次合并：117+5=122
合并的总分值：67+83+96+108+117+122=593，593已是最大分值。

也可以这样合并：
第1次合并：5+9+12=26
第2次合并：13+16+22=51
第3次合并：45+51+26=122
合并的总分值：26+51+122=199，199已是最小分值。

因此此题贪心的方法如下：

（1）保证每次选两堆最多的，合并直至只剩一堆为止，能获得最大得分；
这个和huffman树构造是相同的，不再详述！

（2）保证每次选k堆最少的，合并直至只剩一堆为止，能获得最小得分。
这个是多元huffman树的构造。要注意的是：在合并之前，若n%(k-1)!=1，说明合并到最后一轮时，剩下不是k堆（而是比k堆少），这样算的并不是最小得分，
而必须在合并之前添加若干个为0的虚拟堆，目的为凑成的堆数保证每次都能有k堆合并（包括最后一次）最后合并为1堆。
因此，在合并前作如下处理：

//假设石头每堆个数放于stone[1]~stone[n],且stone[n]之后最多k-1个数组单元为可写;
while (n % (k - 1) != 1)
{
        n++;
        stone[n]=0;
}