文章目录

题目链接:

https://hihocoder.com/problemset/problem/1636?sid=1401840

题意:就是合并石子的问题,只不过这次是有区间限制,只能合并[L,R]这之这么多堆的石子

有了这个限制感觉就没那么好理解dp方程了,因为还要考虑合并成了几堆,所以就还要开一维状态来记录现在是合并成了多少堆,于是dp[i][j][p]表示[i,j]这段区间合并成了p堆的代价,那么就有一个转移方程:
d p [ i ] [ j ] [ p ] = m i n ( d p [ i ] [ j ] [ p ] , d p [ i ] [ k ] [ 1 ] + d p [ k + 1 ] [ j ] [ p 1 ] + c o s t ) dp[i][j][p]=min(dp[i][j][p],dp[i][k][1]+dp[k+1][j][p-1]+cost) dp[i][j][p]=min(dp[i][j][p],dp[i][k][1]+dp[k+1][j][p1]+cost)
就是说枚举断点k,然后前面这一坨是合并成1堆,后面这一坨合并成p-1堆,那么总共就是p堆。
但是我觉得还应该多加一个,前面分成p-1堆,后面是一堆的这种:
d p [ i ] [ j ] [ p ] = m i n ( d p [ i ] [ j ] [ p ] , d p [ i ] [ k ] [ p 1 ] + d p [ k + 1 ] [ j ] [ 1 ] + c o s t ) dp[i][j][p]=min(dp[i][j][p],dp[i][k][p-1]+dp[k+1][j][1]+cost) dp[i][j][p]=min(dp[i][j][p],dp[i][k][p1]+dp[k+1][j][1]+cost)

但是好像只写一个就行,我也不知道为什么,不知道是数据太水了还是理论上就是对的

感觉要是我写的话我还要枚举前面一段分成两堆,后面一段分成p-2堆,然后前面一段分成3堆,后面一段分成p-3堆。。。。。
感觉别人写得真的是好巧妙啊~

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=100+5;
const int inf=0x3f3f3f3f;
int dp[maxn][maxn][maxn];//dp[i][j][p]表示[i,j]区间内分成p堆
int a[maxn],sum[maxn];
int main()
{
	int N,L,R;
	while(cin>>N>>L>>R)
	{
		memset(dp,0x3f,sizeof dp);
		for(int i=1; i<=N; i++)cin>>a[i],sum[i]=sum[i-1]+a[i],dp[i][i][1]=0;
		for(int len=1; len<N; len++)
		for(int i=1; i+len<=N; i++)
		{
			int j=i+len;
			for(int p=2; p<=min(len+1,R); p++) //枚举p堆,最多分成这段长度这么多堆,然后再与给的上线取min 
			{
			 	//剩下的j-k+1这一段要够分p堆才行,所以p<=j-k+1 
				for(int k=i; k<j&&p<=j-k+1; k++)dp[i][j][p]=min(dp[i][j][p],dp[i][k][1]+dp[k+1][j][p-1]);//考虑合成p堆 
				if(p>=L)dp[i][j][1]=min(dp[i][j][1],dp[i][j][p]+sum[j]-sum[i-1]);//考虑合成1堆 
			}
		}
		if(dp[1][N][1]==inf)cout<<0<<endl;
		else cout<<dp[1][N][1]<<endl;
	}
}