51nod-1021 石子归并（区间dp入门）

题目

给出n堆石子，两堆相邻的可以合并，花费为合并后的石子数。求最终合并成一堆要花费最小代价。

分析

区间dp，顾名思义，就是解决一些区间内最优值的问题，通常的时间复杂度为n^2 或者 n^3 而区间dp的大致思路就是首先确定状态初始化dp数组的值，然后枚举区间长度，枚举区间的起始点，（有的题目还需要枚举断点） 由小区间转移到大区间。

最后dp[1][n]往往就是答案。

这个题，s代表区间始点，e代表区间终点，k代表枚举区间内的分割点，状态状态转移方程： $dp[s][e]=min(dp[s][e],dp[s][k]+dp[k+1][e]+value[s][e])$

这里可以预处理下前缀和求区间value

#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define d(x) cout << (x) << endl #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #pragma GCC diagnostic error "-std=c++11" using namespace std; typedef long long ll; const int mod = 1e9 + 7; const int N = 1e2 + 10; const int M = 2e2 + 10; int n; int sum[N]; //前缀和 int dp[N][N]; //第 i 堆到第 j 堆答案 int main() { scanf("%d", &n); for (int i = 1, x; i <= n; i++){ //预处理前缀和，便于后面求区间权值 scanf("%d", &x); sum[i] = sum[i - 1] + x; } for(int len = 2; len <= n; len++){ //枚举区间长度 for (int s = 1; s <= n - len + 1; s++){ //枚举区间起点s int e = s + len - 1; //区间终点 dp[s][e] = INF; for (int k = s; k <= e; k++){ dp[s][e] = min(dp[s][e], dp[s][k] + dp[k + 1][e] + sum[e] - sum[s - 1]); } } } printf("%d\n", dp[1][n]); return 0; }