老是合并可以统一相邻的个别堆积石子。3

分拣标签 Tags 点是开展 

 

动态规划 区间型DP

 

 

代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,s[101],f[101][101];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
     {
         scanf("%d",&s[i]);
         s[i]+=s[i-1];
     }
    memset(f,127,sizeof(f));
    for(int i=1;i<=n;i++)
     f[i][i]=0;
    for(int i=n-1;i>=1;i--)
      for(int j=i+1;j<=n;j++)
        for(int k=i;k<j;k++)
         f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
    printf("%d",f[1][n]); 
    return 0;
}

思路:

题解

dp[i][j] =
min(dp[i][k] +dp[k+1][j]+s[j]-s[i-1]) k属于[i, j];

dp的历程被际很重点

每当输入阶段维护一个sum[i]数组表示前i项的砾的跟

dp[i][j]的意思是归并i~j积石子的顶小代价

定义k为i~j中任意一堆积石子,遍历k找有极端小代价就是是dp[i][j];

区区认为:

 先把每个数之前缀和请出,这样预防了每次合并的时节都务求即刻片只数的与,是代码简单。

 这样随意一个距离内片屡i,j的以及不畏可以代表为:sum[i]-sum[j-1]

 倒着各一个区间进行呼吁最好优解

注意: 

 
 要倒着循环!!!

 
 因为巧着循环时,f[1][1]的值为1,f[2][3]的价为巨大值,这样他就算无法创新其前的价值,也就是说,就算前面的价不是极优解,他也未曾价值好再次给!这样就是无法请出极端优解!

 

样例输出 Sample Output

空间范围: 128000 KB

输出描述 Output Description

日限定: 1 s

一个平头表示最好小集合代价

 题目等级 : 黄金 Gold

题解

 

 

 

题目叙述 Description

有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

数据范围以及提示 Data Size & Hint

 

4 1 1 4

故于区间l到r内枚举断点时单待枚举s[l][r-1]~s[l+1][r]里的触及

输入描述 Input Description

多少范围以及提示 Data Size & Hint

数据范围比“石子归并” 扩大了

第一履一个整数n(n<=3000)

 

样例输入 Sample Input

18

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=3010,inf=1000000000;
int f[maxn][maxn],s[maxn][maxn];
int n,a[maxn],w[maxn][maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        w[i][i]=a[i];
    }
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        w[i][j]=w[i][j-1]+a[j];
    for(int i=1;i<=n;i++)s[i][i]=i;
    for(int p=1;p<n;p++){
        for(int i=1;i<=n-p;i++){
            int j=i+p;
            f[i][j]=inf;
            for(int k=s[i][j-1];k<=s[i+1][j];k++){
                if(f[i][j]>f[i][k]+f[k+1][j]+w[i][j]){
                    f[i][j]=f[i][k]+f[k+1][j]+w[i][j];
                    s[i][j]=k;
                }
            }
        }
    }
    printf("%d",f[1][n]);
}

题材叙述 Description

复杂度降为n^2

遂用基本的做法写出来就TLE,只会得50分

随即道题正确的解法是四止形不等式优化dp,为这开摸底四边形不等式优化措施

这个写和砾石归并1唯一的别就是是数据范围变死了

浅显的游说,就是大半矣一个s[l][r]多次组,用以记录得到l到r区间的极端优解用的凡哪位点作为断点

3002 石子归并 3

4

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

关于s[][]的对的验证本人还尚无会将明白,不了那原理非常明朗,在石子归并问题遭受其断点随区间为右侧走,是来单调性的,因此有s(i,j-1)≤s(i,j)≤s(i+1,j)

发n堆石子排成一列,每堆石子有一个轻重w[i],
每次合并可以统一相邻之鲜积石子,一不成联合的代价呢少积聚石子的分量与w[i]+w[i+1]。问安排什么的统一顺序,能够使总合并代价上最好小。