Codeforces 1013E(DP)

发表于 | 分类于 | | + s

Codeforces 1013E
题意：给你$n$个数，你一次操作可以把某一个数$-1$（可以减为负数），你的目标是使任意的$k$个数严格小于它旁边的两个数（第一个数只用严格小于第二个数，第$n$个数只用严格小于第$n-1$个数），问最少需要几次操作。$k$是不确定的，请输出$k \in[1,\left\lceil\dfrac{n}{2}\right\rceil]$时的答案。(题意来自Luogu)

求最优值，想到DP，并且要求$,\left\lceil\dfrac{n}{2}\right\rceil$个值，所以可以设$dp(i,j)$为前$i$个数有$j$个数满足题意的最优值。但是这样转移非常困难，因为不知道上一个接上的是不是满足题意的值。那么我们设：

dp(i,j,0) 为前$i$个数有$j$个数满足题意，并且$i, i-1$都不满足题意的最优值
dp(i,j,1) 为前$i$个数有$j$个数满足题意，并且$i$满足题意的最优值
dp(i,j,2) 为前$i$个数有$j$个数满足题意，并且$i-1$满足题意的最优值

是否很像树状DP的样子？
然后分别转移：
$$dp(i,j,0)=min(dp(i - 1, j ,0), dp(i - 1, j ,2))$$
这个意思是直接继承之前的，画个图就能搞明白
$$dp(i,j,2)=dp(i - 1, j ,1)+max(0, a_{i} - a_{i - 1} + 1)$$
因为之前$dp(i - 1, j ,1)​$的最后一个满足题意没有考虑现在的$i​$，于是要进行操作。

然后考虑$dp(i,j,1)$
$$s =dp(i - 1,j - 1,0) + max(0, a_{i - 1} - a_{i} + 1)$$
前面两个都不是满足题意的，所以直接操作
$$t=dp(i - 1,j - 1,2) + max(0, min(a_{i - 1}, a_{i - 2} - 1) - a_{i} + 1)$$
前面两个点中$i-2$满足题意，并且$i-1$必然在之前操作中已经小于$i-2$，所以操作要取$min$
$$dp(i,j,1)=min(s, t)$$
综合前面的答案取最小。

初始值：$dp(i,0,0)=0, dp(1,1,1)=1$，其他赋值$∞$
第一个不用解释，第二个因为只有一个数所以必然有一个满足题意的数。
写初值的时候要注意全面考虑，不要忘

然后就可以直接做了

方法二，设$dp(i,j,0/1)$为前$i$个数有$j$个数修房子，并且$i$修(0)/不修(1)房子的最优值
注意转移$dp(i,j,1)​$的时候不要从$i-1​$转移，而是从$i-2​$转移，这样转移非常方便
转移方程：
$dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1] + max(0, a[i] - a[i - 1] + 1))$
$dp[i][j][1] = min(dp[i - 2][j - 1][1] + max(0, a[i - 1] - min(a[i - 2], a[i]) + 1), dp[i - 2][j - 1][0] + max(0, a[i - 1] - a[i] + 1))$

方法一

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, ai[5000 + 5], dp[5005][3005][3];
void clean() {
}
int solve() {
    clean();
    for (int i = 1; i <= n; i++) scanf("%d", &ai[i]);
    for (int i = 0; i <= n; i++) 
    for (int j = 0; j <= (n + 1) / 2; j++) dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = 1000000000;
    for (int i = 1; i <= n; i++) dp[i][0][0] = 0;
    dp[1][1][1] = 0;
    for (int i = 2; i <= n; i++) 
    for (int j = 1; j <= (i + 1) / 2; j++) {
        dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][2]);
        dp[i][j][1] = min(dp[i - 1][j - 1][0] + max(0, ai[i - 1] - ai[i] + 1), dp[i - 1][j - 1][2] + max(0, min(ai[i - 1], ai[i - 2] - 1) - ai[i] + 1));
        dp[i][j][2] = dp[i - 1][j][1] + max(0, ai[i] - ai[i - 1] + 1);
        //printf("i=%d j=%d\n", i, j);
        //printf("%d %d %d\n\n", dp[i][j][0], dp[i][j][1], dp[i][j][2]);
    }
    for (int j = 1; j <= (n + 1) / 2; j++) printf("%d ", min(dp[n][j][0], min(dp[n][j][1], dp[n][j][2])));
    return 0; 
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}

方法二

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

using namespace std;

namespace flyinthesky {  

    const LL MAXN = 5000 + 5;

    LL n, a[MAXN], dp[MAXN][MAXN][2];

    void clean() {
        for (LL i = 0ll; i <= n; i++)
        for (LL j = 0ll; j <= n; j++) dp[i][j][0] = dp[i][j][1] = LONG_LONG_MAX / 2;
    }
    int solve() {
        scanf("%lld", &n);
        clean();
        for (LL i = 1ll; i <= n; i++) scanf("%lld", &a[i]);
        dp[0][0][0] = 0ll, dp[1][0][0] = 0ll, dp[1][1][1] = 0ll;
        for (LL i = 2ll; i <= n; i++)
        for (LL j = 0ll; j <= min(i, (n + 1ll) / 2ll); j++) {
            dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1] + max(0ll, a[i] - a[i - 1] + 1ll));
            if (j >= 1) dp[i][j][1] = min(dp[i - 2][j - 1][1] + max(0ll, a[i - 1] - min(a[i - 2], a[i]) + 1ll), dp[i - 2][j - 1][0] + max(0ll, a[i - 1] - a[i] + 1ll));
        }
        for (LL i = 1ll; i <= (n + 1ll) / 2ll; i++) printf("%lld ", min(dp[n][i][0], dp[n][i][1]));
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------