合并石子 一本通

【题目描述】

在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

计算出将Ｎ堆石子合并成一堆的最小得分。

【输入】

第一行为一个正整数N (2≤Ｎ≤100)；

以下Ｎ行,每行一个正整数，小于10000，分别表示第i堆石子的个数(1≤i≤N)。

【输出】

一个正整数，即最小得分。

【输入样例】

7
13
7
8
16
21
4
18

【输出样例】

239

这是一道区间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;
}