精华内容
下载资源
问答
  • 石子合并

    2017-05-18 21:25:18
    石子合并

    石子合并(NOI1995)

    题目描述
    在操场上沿一直线排列着 n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆, 并将新的一堆石子数记为该次合并的得分。允许在第一次合并前对调一次相邻两堆石子的次序。
    计算在上述条件下将n堆石子合并成一堆的最小得分和初次交换的位置。

    输入
    输入数据共有二行,其中,第1行是石子堆数n≤100;
    第2行是顺序排列的各堆石子数(≤20),每两个数之间用空格分隔。

    输出
    输出合并的最小得分。

    样例输入
    3
    2 5 1
    样例输出
    11

    平行四边形优化

    m(i,j)=min{ m(i,k-1)+m(k,j)+w(i,j)}i< k<=j

    假如对于i<=i’< j<=j’,有w(i’,j)<=w(i,j’),那么我们称函数 w 满足关于区间包含的单调性。

    另外,假如有:w(i,j)+w(i’,j’)<=w(i’,j)+w(i,j’)那么我们称函数 w 满足四边形不等式。

    则可推得m(i,j)也满足四边形不等式,那么s(i,j)单调

    {s[i][j]为(i,j)的最优断点,s[i][i]=i}

    此时m(i,j)=min{ m(i,k-1)+m(k,j)+w(i,j)}s[i][j-1]<= k<=s[i+1][j]

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int a[200],s[200],f[200][200],b[200][200];
    int main(){
      int n;
      scanf("%d",&n);
      for (int i=1;i<=n;++i) scanf("%d",&a[i]);
      int ans=1<<29;
      for (int cas=1;cas<n;++cas){
        swap(a[cas],a[cas+1]);
        s[0]=0;
        for (int i=1;i<=n;++i){s[i]=s[i-1]+a[i];b[i][i]=i;}
        for (int i=1;i<=n;++i)
          for (int j=1;j<=n;++j) f[i][j]=1<<29;
        for (int i=1;i<=n;++i) f[i][i]=0,f[i+1][i]=0;
        for (int l=1;l<=n;++l)
          for (int i=1;i<=n;++i){
            int j=i+l;
            for (int k=b[i][j-1];k<=b[i+1][j];++k)
            if (f[i][k]+f[k+1][j]+s[j]-s[i-1]<f[i][j]){
              f[i][j]=f[i][k]+f[k+1][j]+s[j]-s[i-1];
              b[i][j]=k;
            }
          }
        ans=min(ans,f[1][n]);
        swap(a[cas],a[cas+1]);
      }
      printf("%d",ans);
      return 0;
    }
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,298
精华内容 1,319
关键字:

石子合并