UVALive8177 Pangu and Stones（区域赛铜牌题）
UVALive8177 Pangu and Stones（区域赛铜牌题）
Sample Input
3 2 2
1 2 3
3 2 3
1 2 3
4 3 3
1 2 3 4Sample Output
9
6
0题目来源：2017年某区域赛铜牌题。最近老师发了个题集就和室友组队模拟了一下，一开始遇到这题以为是很普通的优先队列的题目，之后看到有范围限制，立马想到了区间dp，在死磕了一个多小时后依旧答不出的情况下，我去参考了下题解~~~就有了以下的代码，这道题需要开三个维度。
简单翻译：
在中国神话中，盘古是第一个活着的人，是天地万物的创造者。他从鸡蛋中醒来，把鸡蛋分成两部分：天空和大地。
起初，地球上没有山，只有石头遍布大地。有n堆石头，编号从1到N。盘古想把它们全部合并成一堆，建造一座大山。如果几堆石头的总和是s，盘古就需要s秒来把它们堆成一堆，新的一堆石头中就会有s块。
不幸的是，每次盘古只能把连续的桩合并成一个桩。他合并的桩数不应小于L或大于R。
盘古想尽快完成这件事。
你能帮他吗？如果没有解决方案，则应回答“0”。
输入：可以输入多组数据。n，l，r分别表示石头数目，合并堆数只能从l到r，第二行输入n个石头的时间。
输出：如果存在方案，就输出最小的，没有就输出0。
题意：给你一堆石头，要求你每次只能将L到R堆石头合并为一堆，每个石头都有一个时间，每次合并需要的时间等于合并的石头总和。要我们求得合并这堆石头需要的最少时间，如果没有解决方案就输出0。
状态转移：dp[I][j][k]表示从I到j的石头区间里分成k堆的情况
当k=1时，石头可以从L到R堆合并为1堆有dp[I][j][k]=max(dp[I][j][k],dp[I][j][d]+num[j]-num[I-1]，这里的d我们表示堆数目(L<=d<=R)。num是前缀和的数组。
当k!=1时候，石头可以理解为一堆石头A与k-1堆石头B的合并，也就有dp[I][j][k]=max(dp[I][j][k],dp[I][e][1]+dp[e+1][j][k-1])，这里的e表示的是A和B的分界点，也就是普通的区间dp了，接下来的代码就比较清晰了。
#include<iostream>
#include<cstring>
#define mem(s,t) memset(s,t,sizeof(s))
using namespace std;
int dp[105][105][105];
int val[105];
int sum[105];
int main()
{
int n,l,r;
while(cin>>n>>l>>r)
{
mem(sum,0);
for(int i=1;i<=n;i++){
cin>>val[i];
sum[i]=sum[i-1]+val[i]; //求前缀和，方便计算
}
mem(dp,0x3f);
for(int i=1;i<=n;i++){
dp[i][i][1]=0;
}//初始化，每个石头之间没有合并所以他们花费的时间是0
for(int i=2;i<=n;i++){//区间跨度
for(int j=1;j<=n;j++){//起点
int e=i+j-1;
if(e>n)break;//终点不能大于n
for(int k=i;k>=1;k--){//枚举堆数
if(k==1){
for(int z=l;z<=r;z++)
dp[j][e][k]=min(dp[j][e][k],dp[j][e][z]+sum[e]-sum[j-1]);
}else{
for(int z=j;z<e;z++)
dp[j][e][k]=min(dp[j][e][k],dp[j][z][1]+dp[z+1][e][k-1]);
}
}
}
}
if(dp[1][n][1]!=0x3f3f3f3f)cout<<dp[1][n][1]<<endl;
else cout<<0<<endl;
}
}
这是一道算是简单，但是又有技巧的区间dp，一开始不知道要开三维只开两维就推到不出来。所以以后对于动态规划，如果二维不够，可以开三维试试，三维不够就四维~
