作者: hgz 发布时间: 2017-05-20 16:30 

题解

维护前缀和，枚举分割点k

dp[i][j]表示第i到第j堆石子合并的最优值，sum[i][j]表示第i到第j堆石子的总数量。

 

 

平行四边形优化

 

设m[i,j]表示动态规划的状态量。

m[i,j]有类似如下的状态转移方程：

m[i,j]=min{m[i,k]+m[k,j]}(i≤k≤j)

定义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])

记录最佳分割点point[i][j]，k从point[i][j- 1]枚举到point[i + 1][j]即可

CODE

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll; ll pre[110], s[110];ll f[110][110];ll point[110][110];ll n; ll get_min_score(){    ll i, j, k;    for (i = 1; i <= n; i++)        f[i][i] = 0, point[i][i] = i;    for (j = 1; j <= n; j++)    {        for (i = 1; i <= n - j; i++)        {            f[i][i + j] = INT_MAX;            for (k = point[i][i + j - 1]; k <= point[i + 1][i + j]; k++)            {                int tmp = f[i][k] - pre[i - 1] + f[k + 1][i + j] + pre[i + j];                if (tmp < f[i][i + j])                {                    f[i][i + j] = tmp;                    point[i][i + j] = k;                }            }        }    }    return f[1][n];} int main(){    ll i, j, k;    ll global_min = INT_MAX;    scanf("%lld", &n);    for (i = 1; i <= n; i++)        scanf("%lld", &s[i]);    for (i = 1; i < n; i++)    {        swap(s[i], s[i + 1]);        pre[0] = 0;        for (k = 1; k <= n; k++)        {            pre[k] = pre[k - 1] + s[k];        }        global_min = min(global_min, get_min_score());        swap(s[i], s[i + 1]);    }    printf("%lld\n", global_min);    //system("pause");    return 0;}
         
        
       
      

 

 

 

 

 

 

问题 F: 石子合并（NOI1995）

时间限制: 1 Sec  内存限制: 128 MB

提交: 89  解决: 48

 

题目描述

在操场上沿一直线排列着 n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆， 并将新的一堆石子数记为该次合并的得分。允许在第一次合并前对调一次相邻两堆石子的次序。

计算在上述条件下将n堆石子合并成一堆的最小得分和初次交换的位置。

输入

输入数据共有二行，其中，第1行是石子堆数n≤100；

第2行是顺序排列的各堆石子数（≤20），每两个数之间用空格分隔。

输出

输出合并的最小得分。

样例输入

3 2 5 1

样例输出

11