P1775 石子合并（弱化版）
2022-04-29 13:55:05

題面

設(shè)有 (N(N le 300)) 堆石子排成一排，其編號為 (1,2,3,cdots,N)。每堆石子有一定的質(zhì)量 (m_i(m_i le 1000))?，F(xiàn)在要將這 (N) 堆石子合并成為一堆。每次只能合并相鄰的兩堆，合并的代價為這兩堆石子的質(zhì)量之和，合并后與這兩堆石子相鄰的石子將和新堆相鄰。合并時由于選擇的順序不同，合并的總代價也不相同。試找出一種合理的方法，使總的代價最小，并輸出最小代價。

輸入格式

第一行，一個整數(shù) (N)。

第二行，(N) 個整數(shù) (m_i)。

輸出格式

輸出文件僅一個整數(shù)，也就是最小代價。

思路

我永遠喜歡動態(tài)規(guī)劃！

方程：

代碼

#include <bits/stdc++.h>
#define int long long
#define ZYBAKIOI (0x7f)
#define endl ('
')
using namespace std;

int f[1005][1005];

int n;
int a[114514];

struct {
	int sum[114514];
	void add(int i,int v) {
		sum[i]=sum[i-1]+v;
	}
	int query(int l,int r) {
		return sum[r]-sum[l-1];
	}
} qzh;

signed main() {
	cin>>n;
	memset(f,ZYBAKIOI,sizeof(f));
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		qzh.add(i,a[i]);
		f[i][i]=0;
	}
	for(int l=2; l<=n; l++) {
		for(int i=1; i<=n-l+1; i++) {
			int j=i+l-1;
			for(int k=i; k<j; k++) {
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+qzh.query(i,j));
			}
		}
	}
	cout<<f[1][n]<<endl;
	return 0;
}