石子合并简化版（区间DP）

题目链接

https://www.acwing.com/problem/content/284/

思路

因为只能合并相邻的两堆石子，并且首位不构成环，那么我们用 f [ i ] [ j ] f[i][j] f[i][j]表示区间 [ i , j ] [i,j] [i,j]这个范围的一个合并最小值那么我们思考这个状态怎么转移过来，显然的是肯定是从更加细微的区间转移过来，那么我们就对区间进行一个划分操作，我们将其划分为 [ i , k ] [i,k] [i,k]和 [ k + 1 , j ] [k+1,j] [k+1,j]两部分，然后将这两个区间合并，那么我们只需要枚举一下k的位置即可，那么还有一个问题，我们 [ i , k ] [i,k] [i,k]和 [ k + 1 , j ] [k+1,j] [k+1,j]这个区间的值怎么来呢，这个值应该是要从更小的区间长度转移过来，那么我们现在明白了，我们首先枚举的应该是区间长度，我们从长度为2开始枚举，因为刚好这样能花费成两个最小的区间，然后我们再去枚举一下起点位置，有了起点，我们就能知道终点的长度（因为区间长度我们已经枚举了），最后我们枚举一下区间的划分点就好啦，详情请看代码，状态转移方程大概是： f [ l ] [ r ] = m i n ( f [ l ] [ r ] , f [ l ] [ j ] + f [ j + 1 ] [ r ] + s u m ) f[l][r] = min(f[l][r],f[l][j] + f[j+1][r] + sum) f[l][r]=min(f[l][r],f[l][j]+f[j+1][r]+sum) 这里的这个sum表示的是区间 [ l , r ] [l,r] [l,r]的合并值，显然是固定的

代码

#include
using namespace std;

const int N = 3e2+10;
const int INF = 0x3f3f3f3f;
int n,f[N][N],pre[N];

int main()
{
	cin>>n;
	for(int i = 1;i >pre[i],pre[i] += pre[i-1];

	for(int len = 2;len