AtCoder Beginner Contest 229 「F dp」

这篇具有很好参考价值的文章主要介绍了AtCoder Beginner Contest 229 「F dp」。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

F - Make Bipartite

题目描述

给出 $n + 1$ 个点，下标是 $0$ 到 $n$ ，从 $1$ 到 $n$ 都存在一体指向0的带权无向边，边权为ar[i]，同时从 $i$ 到 $i + 1$ 也存在一条带权无向边，边权为 $b r [i]$ ，当然，n指向的不是n+1，是1，即是一个环

问你形成二分图最小需要删除的边的权值之和是多少

思路

要形成二分图，点i可以和 $i - 1$ 连边，也可以跟 $0$ 连边

假设最后形成的二分图进行染色后

如果 $i$ 跟 $i - 1$ 的颜色相同，说明要删除 $b r [i - 1]$ 边

如果 $i$ 跟 $0$ 的颜色相同，说明要删除 $a r [i]$ 边

那我们假设 $0$ 的颜色是0

设 $d p$ 的状态为:

$d p [i] [j] [k] 表示第 i 个点的颜色为 j ，第一个点的颜色为 k$

我们可以通过枚举当前点的颜色和上一个点的颜色来进行状态转移

最后不要忘了计算一下n和1的颜色文章来源地址https://www.toymoban.com/news/detail-519803.html

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

typedef long long ll;
ll mod = 998244353;
#define MAX 1000050
ll n, m, k, x, y, z;
ll ar[MAX], br[MAX];
ll dp[MAX][2][2];

ll min(ll x, ll y){
    return x < y ? x : y;
}

int main(){
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++i)scanf("%lld", &ar[i]);
    for(int i = 1; i <= n; ++i)scanf("%lld", &br[i]);
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0][0] = ar[1];dp[1][1][1] = 0;
    for(int i = 2; i <= n; ++i){
        for(int j = 0; j < 2; ++j){
            for(int pre = 0; pre < 2; ++pre){
                for(int k = 0; k < 2; ++k){
                    dp[i][j][k] = min(dp[i][j][k],dp[i-1][pre][k] +(j == 0 ? ar[i] : 0) +(pre == j ? br[i-1] : 0));
                }
            }
        }
    }
    ll ans = 1e18;
    for(int j = 0; j < 2; ++j){
        for(int k = 0; k < 2; ++k){
            ans = min(ans, dp[n][j][k] + (j==k?br[n]:0));
        }
    }
    printf("%lld\n", ans);
    return 0;
}