阿祁的部落格

ZeroJudge h663 - 士兵排列(Soldiers) 解題心得( 題目 )

解題概念:DP(類TSP問題)

解題方法:這題如果枚舉所有組合是O(N!)，顯然不夠好。

那我們怎麼辦呢，我們注意到只有相鄰的兩個士兵會產生關係，因此我們可以定義DP[S][end]代表我們已填入集合S裡面的所有士兵，以及目前的對列結尾為end，在這情形下的最小cost，這樣我們複雜度可以化為指數型態，為(N^2)*(2^N)，雖然還是很糟，但比階乘好了。

仔細看發現這題其實很像TSP問題，但是這題還需要輸出最小字典序排列，我的方法是在DP時盡量讓後面越小越好，之後紀錄之前轉移的來源(也就是最小解的前個來源)，利用backtrack找回去，為O(N)。

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

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

//Date:2022/04/05

import java.util.*;

import java.io.*;

public class zjh663 {

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

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

    public static int ret,rd;

    public static pii[][] DP=new pii[1<<18][18];

    public static int[][] cost=new int[18][18];

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

        final int n=readint();

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

            for(int j=0;j<n;j++) {

                cost[i][j]=readint();

            }

        }

        for(int i=0,j=0;j<n;j++) {

            DP[i][j]=new pii(-1,-1,0);//initial state

        }

        int min,o;

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

            for(int j=0,k=1;j<n;j++,k<<=1) {

                min=(1<<30);

                if((i&k)!=k) {

                    DP[i][j]=new pii(-1,-1,(1<<29));//if k is not in i yet

                    continue;

                }

                for(int l=0;l<n;l++) {

                    o=DP[i^k][l].v+cost[l][j];

                    if(o<min) {

                        min=o;

                        DP[i][j]=new pii(i^k,l,o);

                    }

                }

            }

        }

        pii ans=null;

        int ptr=1,set=(1<<n)-1,nxt;

        min=(1<<30);

        for(int l=0;l<n;l++) {  //find min

            o=DP[set][l].v;

            if(o<min) {

                min=o;

                ans=DP[set][l];

                ptr=l;

            }

        }

        System.out.println(ans.v);

        for(int i=0;i<n;i++) {  //find permutation

            System.out.print((ptr+1)+" ");

            if(i==n-1)break;

            nxt=DP[set][ptr].p;

            set=DP[set][ptr].ps;

            ptr=nxt;

            ans=DP[set][ptr];

        }

        System.out.println();

    }

    

    public static int readint() throws Exception{

        ret=0;

        rd=br.read();

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

            ret*=10;

            ret+=(rd&15);

            rd=br.read();

        }

        return ret;

    }

}



class pii{

    int ps,p,v;

    pii(int a,int aa,int b){

        ps=a;

        p=aa;

        v=b;

    }

}