0%

Codeforces 1012C Hills 比较简单的DP

刚刚拿到一个夏令营的offer,顺便在附近城市玩了两天,算起来出门在外有10天了?重新开始补题。


题目链接

题意:输入一串数字代表一串山坡的高度,可以建房子的山坡的定义是这个山坡的高度严格比旁边两个山坡大。我可以用挖掘机挖山坡使其高度-1(可以减到负数)。现在要分别找到想建1-n/2个房子,问要挖掉的总高度的最小值。(n:5e3)

从题目知道我们房子显然不能两个贴在一起放,如果第i个山坡修了房子,则第i+1个山坡一定放不了房子,然后第i+2个山坡的左侧山坡可能在修第i个山坡的时候被挖掉了一块。所以i只对i+1和i+2都有影响。

直观的思想:定义dp[i][j][k],i为现在计算第i个山坡的情况(如果空间不足可以滚动),j代表之前的这段区间修了j个房子,k代表上个房子的位置,状态取值为0-2,分别代表上个房子在很早以前(即对i无影响)、在第i个山坡、在第i-1个山坡(影响修i的时候挖掉的面积)。值为修到这里需要挖走的最小高度。

转移公式为:

dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j][2]);

dp[i][j][1] = min( dp[i-1][j][0]+max(0, h[i-1]-h[i]+1), dp[i-1][j][2]+max(0, max(0, min(h[i-2]-1, h[i-1]) - h[i] + 1 )(从2状态转移,提前计算i-1现在的高度)

dp[i][j][2] = dp[i-1][j][1]

然后我写了long long 的数组,悲剧的发现爆内存了,尤其是发现别人用int写的三种状态并没有爆内存。

然后发现所有2状态可以用公式3替换掉。但是需要注意的是这样的话最后求解对每个j需要算:min(dp[n-1][j][0], dp[n-1][j][1], dp[n-2][j][1])。这里很容易把第三项丢掉。

然后注意一下初始化,判断一下n=1的情况和边界,然后注意一下输出k的取值是(n+1)/2就可以了。

代码:

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 3;
const long long MAXLL = 9e18;
long long h[MAXN];
long long dp[MAXN][MAXN][2]; //last is i, now has j
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%lld", &h[i]);
}
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= n; j++)
{
dp[i][j][0] = MAXLL;
dp[i][j][1] = MAXLL;
}
}
for(int i = 0; i < n; i++)dp[i][0][0] = 0LL;
if(n == 1)
{
printf("0\n");return 0;
}
if(n > 1)dp[0][1][1] = max(0LL, h[1] - h[0] + 1LL);
for(int i = 2; i < n; i++)dp[0][i][0] = dp[0][i][1]= MAXLL;
for(int i = 1; i < n; i++)
{
for(int j = 1; j <= i/2 + 1; j++)
{
dp[i][j][0] = dp[i-1][j][0];
if(i > 1)dp[i][j][0] = min(dp[i][j][0], dp[i-2][j][1]);
dp[i][j][1] = dp[i-1][j-1][0] + max(0LL, h[i-1] - h[i] + 1LL);
if(i > 1){dp[i][j][1] = min(dp[i][j][1], dp[i-2][j-1][1] + max(0LL, min(h[i-2]-1LL, h[i-1]) - h[i] + 1LL));}
if(i < n-1)dp[i][j][1] += max(0LL, h[i+1] - h[i] + 1LL);
//dp[i][j][2] = dp[i-1][j][1];
}
}
/*for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)printf("%lld:%lld ", dp[i][j][0], dp[i][j][1]);printf("\n");
}*/
long long ans = 0;
for(int i = 1; i <= (n+1)/2; i++){
ans = min(dp[n-1][i][0], min(dp[n-1][i][1], dp[n-2][i][1]));
printf("%lld%c", ans, i == n/2+1? '\n' : ' ');
}

return 0;
}
-------------这么快就看完啦^ω^谢谢阅读哟-------------