HihoCoder-1636(三维区间dp)

题目传送门 :HihoCoder-1636

题目大意:

石子归并,只不过第一行除了给出n,还给出L,R。
每次合并必须合并相邻的k堆(L<=k<=R)
求能不能合并成一堆,不能的话输出0,否则输出最小代价。

思路

北京现场赛的铜牌题,是个三维的区间dp,之前做的区间dp都是二维,这次懵逼了。
dp[i][j][k]代表区间i-j分成k堆的最小代价。
f(i,j,1) = min( f(i,k,p)+f(k+1,j,1)+sum(i,j) )(k = 1);
f(i,j,k) = min( f(i,p,k-1)+f(p+1,j,1) )(k > 1)
关键就是枚举的时候,要把堆按照k-1堆和1堆合并来枚举答案,这样枚举复杂度是n^2,否则情况太复杂
分成一堆的情况比较好想,注意枚举p的范围是[L-1,R-1];
分成k堆的时候,注意不要+sum(i,j),因为k-1堆和1堆一共是k堆,并没有合并。
这样总的时间复杂度是n^4。
热身赛测机器时1e8的数据大概150ms,复杂度完全符合题目要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <cctype>
#include <set>
#include <ctype.h>
#include <string.h>
#define inf 0x3f3f3f3f
#define eps 0.0000001
using namespace std;
typedef long long ll;
typedef pair<int , int> P;
const int maxn = 100 + 10;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int dp[maxn][maxn][maxn];
int a[maxn],sum[maxn];
int n,L,R;
int main(int argc, char const *argv[])
{
while(cin >> n >> L >> R){
for(int i = 1 ; i <= n ; i ++){
cin >> a[i];
}
memset(dp,inf,sizeof(dp));
memset(sum,0,sizeof(sum));
for(int i = 1 ; i <= n ; i ++){
sum[i] = sum[i-1] + a[i];
}
for(int i = 1 ; i <= n ; i ++){
for(int j = i ; j <= n ; j ++){
dp[i][j][j-i+1] = 0;
}
}
for(int len = 0 ; len <= n ; len ++){
for(int i = 1 ; i + len -1 <= n ; i ++){
int j = i + len - 1;
for(int k = i ; k < j ; k ++){
for(int p = L-1 ; p < R ; p ++){
dp[i][j][1] = min(dp[i][j][1] , dp[i][k][p] + dp[k+1][j][1] + sum[j]-sum[i-1]);
}
}
for(int k = 2 ; k <= len ; k ++){
for(int p = i ; p < j ; p ++){
dp[i][j][k] = min(dp[i][j][k] , dp[i][p][k-1] + dp[p+1][j][1]);
}
}
}
}
if(dp[1][n][1] == inf){
cout << 0 << endl;
}
else{
cout << dp[1][n][1] << endl;
}
}
return 0;
}