阿祁的部落格

CSES 2181 - Counting Tillings 解題心得( 題目 )

解題概念:DP

解題方法:利用輪廓線DP，判斷目前決策點是否已經有骨牌，枚舉討論各種輪廓的解。

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

import java.io.*;

import java.util.*;

import java.math.*;

public class cses2181 {

    public static int ret,r;

    public static int n,m,max,id=0,x,ans;

    public static final int mod=1000000007;

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

    public static int[][] dp=new int[2][1<<11];

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

        n=readint();

        m=readint();

        solve();

        System.out.println(ans);

      }

      

    public static void solve() {

        max=(1<<(n+1));

        dp[0][0]=1;

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

            DP();

            roll();

        }

        ans=dp[id][0]%mod;

    }



    public static void DP() {

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

            Arrays.fill(dp[id^1],0);

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

                x=(j&(3<<i))>>i;

                if(x==0) {

                    dp[id^1][j+(1<<i)]+=dp[id][j];

                    dp[id^1][j+(2<<i)]+=dp[id][j];

                    dp[id^1][j+(1<<i)]%=mod;

                    dp[id^1][j+(2<<i)]%=mod;

                }

                else if(x==3) {

                    continue;

                }

                else {

                    dp[id^1][j-(x<<i)]+=dp[id][j];

                    dp[id^1][j-(x<<i)]%=mod;

                }

            }

            id^=1;

        }

    }

    

    public static void roll() {

        Arrays.fill(dp[id^1],0);

        for(int i=0;i<(max>>1);i++) {

            dp[id^1][(i<<1)]=dp[id][i];

        }

        id^=1;

    }

    

    public static int readint() throws Exception {

        ret=0;

        r=br.read();

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

            ret*=10;

            ret+=(r&15);

            r=br.read();

        }

        return ret;

    }

}