阿祁的部落格

ZeroJudge c543 - 階梯數字 解題心得( 題目 )

解題概念:數位DP

解題方法:分兩種狀況討論，複雜度O(kN) k=10

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

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

//Date:2022/04/05

import java.util.*;

import java.io.*;

public class zjc543 implements Runnable{

    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,cnt=0;

    public static final int mod=(int)Math.pow(10,9)+7;

    public static long[][] dp=new long[100005][10];

    public static String in;

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

        new Thread(null,new zjc543(),"",1<<26).start();

    }

    

    public void run() {

        try {

            while(true) {

                in=br.readLine();

                if(in==null||in.length()==0)break;

                solve();

            }

            bw.flush();

        }

        catch(Exception e) {

            System.out.println(1/0);//catch RE

        }

        

    }

    public static void solve() throws Exception{

        for(int i=0;i<in.length();i++) {

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

                dp[i][j]=0;

            }

        }

        long o=DP(0,0)-1+mod;

        o%=mod;

        bw.write(o+"\n");

    }

    

    public static long DP(int x,int n) {

        if(x==in.length())return 1;

        long cnt=0;

        for(int i=n;i<in.charAt(x)-'0';i++) {

            cnt+=free(x+1,i);

        }

        if(n<=in.charAt(x)-'0')cnt+=DP(x+1,in.charAt(x)-'0');

        cnt%=mod;

        return cnt;

    }

    

    public static long free(int x,int n) {

        if(x==in.length())return 1;

        if(dp[x][n]!=0) {

            return dp[x][n];

        }

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

            dp[x][n]+=free(x+1,i);

        }

        dp[x][n]%=mod;

        return dp[x][n];

    }

}