F - Make Bipartite

题目描述

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

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

思路

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

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

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

• 如果i跟0的颜色相同，说明要删除ar[i]边

那我们假设0的颜色是0

设$dp$的状态为:

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

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

最后不要忘了计算一下n和1的颜色

#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;
}