【p1880】石子合并

忘是亡心i 2022-06-06 01:55 133阅读 0赞

[https://www.luogu.org/problem/show?pid=1880][https_www.luogu.org_problem_show_pid_1880]

## 1. ##

先从线性的开始吧。

有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。  
样例：  
\[输入\]  
3  
1 2 3  
7  
13 7 8 16 21 4 18  
\[输出\]  
9  
239

由于是相邻两个进行合并，贪心算法并不是最优的算法（比如第二组）。  
可以用区间DP来解决。  
状态：设f\[i\]\[j\]表示从第i堆到第j堆得石子中所需的最小代价  
决策：在区间\[i,j)中枚举一个k，则f\[i\]\[j\] = min(f\[i\]\[k\] + f\[k+1\]\[j\] + s\[i\]\[j\]);  
其中s\[i\]\[j\]表示这段区间的石子数。  
用i枚举上界，用l来枚举区间长度，那么`j = i + l;`  
k来枚举区间中选定的那一堆。  
时间复杂度为O（n^3）

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<cstdio>
    #define N 50
    #define INF 100000
    using namespace std;
    
    inline int read(){
           char c;
           int res,flag = 0;
           while((c = getchar())>'9'||c<'0')
                    if(c=='-')flag = 1;
           res = c - '0';
           while((c = getchar())>='0'&&c<='9')
           res =(res<<3)+(res<<1) + c - '0';
           return flag?-res:res;
    }
    int sum[N+1];
    int f[N][N];
    int main(){
        int n = read();
        sum[0] = 0;
        for (int i =1;i<=n;i++){
            int x;
            x = read();
            sum[i]  = sum[i-1] + x; 
        }
        memset(f,0,sizeof(f));
        for (int l=2;l<=n;l++){
            for (int i=1;i<=n-l+1;i++){
       //要加1
                int j =i + l -1 ;
                f[i][j] = INF;
                for (int k =i;k<j;k++)
                    f[i][j] = min(f[i][j],f[i][k]+f[k+1][j] + sum[j] - sum[i-1]);
            }
        }
        cout<<f[1][n];
    }

可以用平行四边形优化来降低时间复杂度。  
[来自百度百科的解释][Link 1]

> 如果对于任意的a1≤a2 < b1≤b2，  
> 有m\[a1,b1\]+m\[a2,b2\]≤m\[a1,b2\]+m\[a2,b1\]，那么m\[i,j\]满足四边形不等式。
> 
> 设m\[i,j\]表示动态规划的状态量。  
> m\[i,j\]有类似如下的状态转移方程：  
> m\[i,j\]=min\{m\[i,k\]+m\[k,j\]\}(i≤k≤j)  
> m满足四边形不等式是适用这种优化方法的必要条件  
> 对于一道具体的题目，我们首先要证明它满足这个条件，一般来说用数学归纳法证明，根据题目的不同而不同。  
> 通常的动态规划的复杂度是O(n^3)，我们可以优化到O(n^2)  
> 定义s(i,j)为函数m(i,j)对应的使得m(i,j)取得最小值的k值。  
> 我们可以证明，s\[i,j-1\]≤s\[i,j\]≤s\[i+1,j\]  
> 那么改变状态转移方程为：  
> m\[i,j\]=min\{m\[i,k\]+m\[k,j\]\}(s\[i,j-1\]≤k≤s\[i+1,j\])  
> 复杂度分析：不难看出，复杂度决定于s的值，以求m\[i,i+L\]为例，  
> (s\[2,L+1\]-s\[1,L\])+(s\[3,L+2\]-s\[2,L+1\])…+(s\[n-L+1,n\]-s\[n-L,n-1\])=s\[n-L+1,n\]-s\[1,L\]≤n  
> 所以总复杂度是O(n)  
> 以上所给出的状态转移方程只是一种比较一般的，其实，很多状态转移方程都满足四边形不等式优化的条件。  
> 解决这类问题的大概步骤是：  
> 证明w满足四边形不等式，这里w是m的附属量，形如m\[i,j\]=opt\{m\[i,k\]+m\[k,j\]+w\[i,j\]\}，此时大多要先证明w满足条件才能进一步证明m满足条件  
> 证明m满足四边形不等式  
> 证明s\[i,j-1\]≤s\[i,j\]≤s\[i+1,j\]

w\[a,c\]+w\[b,d\]<=w\[b,c\]+wa,d 就称其满足凸四边形不等式  
或打表观察w\[i\]\[j+1\]-w\[i\]\[j\]关于i的表达式，如果关于i递减，则w满足凸四边形不等式  
如果一个函数w\[i\]\[j\]，满足 w\[i’\]\[j\]<=w\[i\]\[j’\] i<=i’<=j<=j’ 则称w关于区间包含关系单调  
如果w同时满足四边形不等式和区间单调关系，则dp也满足四边形不等式

--------------------

## 2. ##

如果石子是环形排列的，由于k是我们枚举的，可以保证在1到n里，但是K+1和j可能会超出范围。因此f\[i\]\[j\] = min(f\[i\]\[k\]+f\[(i+k+1)%n\]\[j-k-1\]+sum\[i\]\[i+j\]),其中对于sum\[i\]\[i+j\]

--------------------

参考：[http://blog.csdn.net/bnmjmz/article/details/41308919][http_blog.csdn.net_bnmjmz_article_details_41308919]  
[http://blog.csdn.net/acdreamers/article/details/18039073][http_blog.csdn.net_acdreamers_article_details_18039073]  
[https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1880][https_www.luogu.org_wiki_show_name_E9_A2_98_E8_A7_A3_P1880]

[https_www.luogu.org_problem_show_pid_1880]: https://www.luogu.org/problem/show?pid=1880
[Link 1]: https://baike.baidu.com/item/%E5%9B%9B%E8%BE%B9%E5%BD%A2%E4%B8%8D%E7%AD%89%E5%BC%8F?fr=aladdin
[http_blog.csdn.net_bnmjmz_article_details_41308919]: http://blog.csdn.net/bnmjmz/article/details/41308919
[http_blog.csdn.net_acdreamers_article_details_18039073]: http://blog.csdn.net/acdreamers/article/details/18039073
[https_www.luogu.org_wiki_show_name_E9_A2_98_E8_A7_A3_P1880]: https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1880