阿祁的部落格

AtCoder ABC 229F - Make Bipartite 解題心得( 題目 )

解題概念:DP

解題方法:首先我們根據定義每一個點以填入0或1表示，而相同數字間不能連線，我們令0號點值為0，令DP[i][j][k]=m 代表討論前i個，且第i個填j色、第一個填k色的最佳解m，列轉移式判斷是否有牴觸去求即可。

Java參考程式碼(有更好意見可留言於下方，謝謝!)

//Author:En Chi Tsung(欉恩祁)

//Date:2021/12/12

import java.util.*;

import java.io.*;

public class Main {

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static int ret,r,id=0;

    public static long[][][] dp=new long[2][2][2];

    public static long[] incost=new long[200005];

    public static long[] outcost=new long[200005];

    public static void main(String[] args) throws Exception{

        final int n=orz();

        for(int i=1;i<=n;i++)incost[i]=orz();

        for(int i=1;i<=n;i++)outcost[i]=orz();

        dp[0][0][0]=0;

        dp[0][1][1]=incost[1];

        dp[0][0][1]=dp[0][1][0]=(1L<<60);

        for(int i=2;i<=n;i++) {

            dp[id^1][0][0]=Math.min(dp[id][0][1], dp[id][0][0]+outcost[i-1]);

            dp[id^1][0][1]=incost[i]+Math.min(dp[id][0][0], dp[id][0][1]+outcost[i-1]);

            dp[id^1][1][0]=Math.min(dp[id][1][1], dp[id][1][0]+outcost[i-1]);

            dp[id^1][1][1]=incost[i]+Math.min(dp[id][1][0], dp[id][1][1]+outcost[i-1]);

            id^=1;

        }

        long ans=Math.min(dp[id][0][0]+outcost[n],dp[id][0][1]);

        ans=Math.min(ans,dp[id][1][0]);

        ans=Math.min(ans,dp[id][1][1]+outcost[n]);

        System.out.println(ans);

    }

    

    public static int orz() throws Exception{

              //輸入

        ret=0;

        r=br.read();

        while(r>47&&r<58) {

            ret*=10;

            ret+=(r&15);

            r=br.read();

        }

        return ret;

    }

}