codevs1048 石子归并(区间DP)

题目描述 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 1 1 4

样例输出 Sample Output

区间dp

d[i][j] 表示合并区间[i,j]的最小代价。

方程:

d[i][j] = min(d[i][k] + d[k+1][j]) + sum(i,j) , 其中,i <= k < j.

可以理解为合并区间[i,j]的方案分解为先合并区间[i,k],再合并区间[k,j],最后将两区间合并.取其中最小代价的一个方案.

sum(i,j)表示[i,j]区间石子的重量和,预处理出前缀和就可以快速求得了。

#include<iostream>
#include<cassert>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<iterator>
#include<cstdlib>
#include<vector>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define rep(i,f,t) for(int i = (f),_end_=(t); i <= _end_; ++i)
#define rep2(i,f,t) for(int i = (f),_end_=(t); i < _end_; ++i)
#define dep(i,f,t) for(int i = (f),_end_=(t); i >= _end_; --i)
#define dep2(i,f,t) for(int i = (f),_end_=(t); i > _end_; --i)
#define clr(c, x) memset(c, x, sizeof(c) )
typedef long long int64;
const int INF = 0x5f5f5f5f;
const double eps = 1e-8;


//*****************************************************

int d[110][110];
int w[110];
int s[110];
int sum(int i,int j){return s[j] - s[i-1];}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i){scanf("%d",w+i);s[i] = s[i-1]+w[i];}
    if(n == 1){
        printf("0
");
        return 0;
    }

    for(int i = n; i >= 1; --i){
        for(int j = i+1; j <= n;++j){
            int sij = sum(i,j);
            d[i][j] = min(d[i+1][j], d[i][j-1]) + sij;
            for(int k = i+1; k < j-1; ++k)
                d[i][j] = min(d[i][j], d[i][k] + d[k+1][j] + sij);
        }
    }
    cout<<d[1][n]<<endl;
    return 0;
}