传送门link
石子合并（弱化版）
题目描述
设有 \(N(N \le 300)\) 堆石子排成一排，其编号为 \(1,2,3,\cdots,N\)。每堆石子有一定的质量 \(m_i\ (m_i \le 1000)\)。现在要将这 \(N\) 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。
输入格式
第一行，一个整数 \(N\)。
第二行，\(N\) 个整数 \(m_i\)。
输出格式
输出文件仅一个整数，也就是最小代价。
样例 #1
样例输入 #1
4
2 5 3 1
样例输出 #1
22
题目思路
我们先简化该题：假设有两个石子堆\(l...k\), \(k+1...r\)，将他们合并的最小代价就是\(a_{l...k}+a_{k+1...r}\)也就是\(a_{l...r}\)，我们的所有石子堆最小合并代价问题都可以分解成这样的形式。
定义状态： \(f_{l,r}\) 表示 \(l...r\) 的石子堆合并最小代价。
转移方程： \(f_{l,r}=min(f_{l,r},f_{l,k}+f_{k+1,r}+a_{l...r})\)
代码
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,a[310],f[310][310],s;
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){for(int l=1,r=i;r<=n;l++,r++){if(l==r)f[l][r]=0;//处理边界else{s=0;for(int k=l;k<=r;k++)s+=a[k];//求a[l...k]的总和f[l][r]=1<<30;//取最小，所以先放个取值较大的数for(int k=l;k<r;k++)f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s);//枚举，将l...r在第k个分成第二段，取值较小的}}}cout<<f[1][n];//输出a[1...n]的最小合并代价return 0;
}