Pangu and Stones (hihocoder 1636)

本文主要是介绍Pangu and Stones (hihocoder 1636)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：

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

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

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

这篇关于Pangu and Stones (hihocoder 1636)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---