石子合并
原题链接:282. 石子合并 - AcWing题库
解题思路
解题方式:dp
状态表示:f[i][j]表示将第i堆石子到第j堆石子合并的所有方式
属性:min
状态转移:
我们需要知道f[i][j]是由那两个区间合并得来的。
而在左右端点已经固定下来的情况下我们只需要知道在区间里已哪个点作为两个区间的中间点就可以(k)就可以了。
i______________j
^
i______k
k+1____j
如图所示,f[i][k]可以由f[i][k]和f[k + 1][j]合并而来
而这次合并包括了区间内的每一堆石子所以这次合并所花的体力就是区间内的质量之和,我们可以用前缀和(s[i] - s[j 1])表示
所以合并到f[i][j]所需的体力就是本次的体力(s[i] - s[j 1])和和并出f[i][k]和f[k + 1][j]所需的体力(f[i][k] + f[k + 1][j])之和
加上求求最小值之后状态转移方程就是: min(f[i][j],f[i][k] + f[k + 1][j] + s[i] - s[j - 1])
源代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 310;
const int INF = 0x3f3f3f;
int n;
int s[N];
int f[N][N];
int main()
{
//输入
cin >> n;
for(int i = 1;i <= n;i ++)scanf("%d",&s[i]);//输入石子堆质量
for(int i = 1;i <= n;i ++)s[i] += s[i - 1];//构造前缀和数组
//dp
for(int l = 2;l <= n;l ++)//枚举区间长度
{
for(int i = 1;i + l - 1 <= n;i ++)//枚举区间起点
{
int le = i;int ri = i + l - 1;//确定区间左右端点(状态表示中的i和j)
f[le][ri] = INF;
for(int k = le;k < ri;k ++)//枚举区间内合并的中间点
{
f[le][ri] = min(f[le][ri],f[le][k] + f[k + 1][ri] + s[ri] - s[le - 1]);//状态转移
}
}
}
cout << f[1][n];
return 0;
}