刚刚拿到一个夏令营的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;
long long dp; //last is i, now has j
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%lld", &h);
}
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= n; j++)
{
dp = MAXLL;
dp = MAXLL;
}
}
for(int i = 0; i < n; i++)dp = 0LL;
if(n == 1)
{
printf("0\n");return 0;
}
if(n > 1)dp = max(0LL, h - h + 1LL);
for(int i = 2; i < n; i++)dp = dp= MAXLL;
for(int i = 1; i < n; i++)
{
for(int j = 1; j <= i/2 + 1; j++)
{
dp = dp;
if(i > 1)dp = min(dp, dp);
dp = dp + max(0LL, h - h + 1LL);
if(i > 1){dp = min(dp, dp + max(0LL, min(h-1LL, h) - h + 1LL));}
if(i < n-1)dp += max(0LL, h - h + 1LL);
//dp = dp;
}
}
/*for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)printf("%lld:%lld ", dp, dp);printf("\n");
}*/
long long ans = 0;
for(int i = 1; i <= (n+1)/2; i++){
ans = min(dp, min(dp, dp));
printf("%lld%c", ans, i == n/2+1? '\n' : ' ');
}
return 0;
}
|