P1775. 石子合并（弱化版）

洛谷上有人说过：dp有两种另类的解法，分别是记忆化搜素和？？贪心

（*笑点解析：前面那两个字忘了

因为我没脑子不会dp，更想不出来状态转移方程

考虑记忆化搜索

不想写了，剩下的都在代码里（笑

#include<iostream>
using namespace std;
int n,a[305],dp[305][305];//dp[i][j]表示合并a[i]-a[j]区间内的石子的最小代价 
//----------------------核心代码--------------------------- 
int dfs(int l,int r){//搜索a[i]-a[j]区间内的石子的最小代价并赋值给dp[i][j] 
	if(l==r) return 0;//自己和自己合并没有代价 
	if(dp[l][r]!=1919810) return dp[l][r];//搜过了直接返回 
	for(int i=l;i<r;i++){//没有搜过的枚举应该在哪里把石子分成两堆,能使得合并代价最小 个人认为这种思路类似于Floyd算法 
		dp[l][r]=min(dp[l][r],dfs(l,i)+dfs(i+1,r)+a[r]-a[l-1]);//选最小值 
	}//dfs(l,i)+dfs(i+1,r)很好理解,重点是后面的a[r]-a[l-1]
	//随便举个例子：1 6 5 8 
	//我想要合成1和6变成7,他并不是直接变成代价为7的一堆石子,而是要先用1+6=7的代价去合成,所以这一堆的代价实际上是14 
	return dp[l][r];// 
}
//----------------------核心代码--------------------------- 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];//输入并预处理前缀和 
	for(int i=0;i<305;i++){
		for(int j=0;j<305;j++){
			dp[i][j]=1919810;//初始化 
		}
	}
	cout<<dfs(1,n);//对整个数组搜索
	return 0;
}
//申达股份给我IE规委会谷物圈和U工会王企鹅法规全额给回复iUI土规u1u挂号费过户UI  

//DFS写法
#include<iostream>
#include<climits>
using namespace std;
const int maxn=1E3+10;
int n, m[maxn], dp[maxn][maxn], pre_sum[maxn];int dfs(int l,int r){
	if(l==r)	return dp[l][r]=0;//1改掉本轮成本dp[l][r]=m[l];一个石头没有合并代价 
	if(dp[l][r])	return dp[l][r];
	int res=INT_MAX;
	for(int k=l;k<r;k++){
		int temp=dfs(l,k)+dfs(k+1,r)+pre_sum[r]-pre_sum[l-1];//2合并过程加上合并代价 
		res=min(res, temp);
	}
	return dp[l][r]=res;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m[i];
		pre_sum[i]=pre_sum[i-1]+m[i];//前缀和加速区间代价计算 
	}
	cout<<dfs(1,n);
	return 0;
}*/

//对着递归代码改DP即可 
#include<iostream>
#include<climits>
using namespace std;
const int maxn=1E3+10;
int n, m[maxn], dp[maxn][maxn], pre_sum[maxn];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m[i];
		pre_sum[i]=pre_sum[i-1]+m[i];//前缀和加速区间代价计算 
	}
	for(int l=n;l>=1;l--){//注意容易写错成for(int l=1;l<=n;l++)。正确应该要区间短→区间长扩展，要么枚举l和长度，如果枚举l\r就可以通过一正一反的方式巧妙扩展 
		dp[l][l]=0;
		for(int r=l+1;r<=n;r++){
			dp[l][r]=INT_MAX;
			for(int k=l;k<r;k++){
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+pre_sum[r]-pre_sum[l-1]);
			}
		}
	}
	cout<<dp[1][n];
	return 0;
}