合并石子 一本通

这是一道区间DP的经典/入门题

状态的表示:f[i][j] 表示合并从 i 到 j 堆的最小得分

可以把 [i,j] 取一个 k 值,分成两个更小的子区间,不断分解,即 f[i][j] → f[i][k]+f[k+1][j]

而在合并的过程中,需要付出分数,而付出的分数就是这两个端点之间的前缀和

初始化:f[i][i] = 0

状态的转移:f[i][j]=min{f[i][j],f[i][k]+f[k+1][j]+sum[j]−sum[i−1]}


前缀和是一种重要的预处理,能大大降低查询的时间复杂度。

最简单的一道题就是给定 n 个数和 m 次询问,每次询问一段区间的和。求一个 O(n + m) 的做法。

用 O(n) 前缀和预处理,O(m) 询问。

for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
while(m--)
 {
     int L, R; scanf("%d%d", &L, &R);
     printf("%d\n", sum[R] - sum[L - 1]);
 }


#include<bits/stdc++.h>
using namespace std;
int n,a[110],s[110],f[110][110];
int main()
{
	cin>>n;
	for(int i=1; i<=n;i++)
	cin>>a[i],s[i]=s[i-1]+a[i];
	
	memset(f,0x0f,sizeof(f));
	
	for(int i=1; i<=n;  i++) f[i][i]=0;
	for(int i=n-1; i>=1; i--)
	for(int j=i+1;j<=n;j++)
	for(int k=i;k<=j-1;k++)
	f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
	
	cout<<f[1][n];
		
	
	return 0;
}