hdu 2089 数位dp

不要62

具有教科书性质的数位dp应用实例。

/** Aug 31, 2015 9:57:30 PM
 * PrjName:hdu2089
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    /**
     * @param args
     */
    final static int maxl=7;
    static int[][] f;
    static int[] digit;
    static void init(){
        f=new int[maxl+1][10];
        f[0][0]=1;
        for(int i=1;i<=maxl;i++)//从低位到高位！
            for(int j=0;j<10;j++)
                for(int k=0;k<10;k++)
                    if (k!=4&&!(j==6&&k==2))
                        f[i][j]+=f[i-1][k];
    }
    static int solve(int n){
        //if (n==0) return 1;
        digit=new int[maxl+1];
        while(n>0){
            digit[++digit[0]]=n%10;
            n/=10;
        }
        int res=0;
        for(int i=digit[0];i>0;i--){//从高位到低位！
            for(int j=0;j<digit[i];j++)
                if(j!=4&&!(j==2&&digit[i+1]==6))//限制前j位，枚举后digit[0]-j位
                    res+=f[i][j];
            if(digit[i]==4||digit[i]==2&&digit[i+1]==6) break;
        }
        return res;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
        PrintWriter out=new PrintWriter(System.out);
        init();
        while(in.nextToken()!=StreamTokenizer.TT_EOF){
            int n=(int)in.nval;
            in.nextToken();
            int m=(int)in.nval;
            if (n==0&&m==0) break;
            //out.println(solve(n)+" "+solve(m+1));
            out.println(solve(m+1)-solve(n));
        }
        out.flush();
        out.close();
    }
}

/** Sep 1, 2015 8:57:53 PM
 * PrjName:hdu2089-2
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
	/**
	 * @param args
	 */
	final static int maxl = 8;
	static int[][] f, g;
	static int[] digit;
	static void init() {
		f = new int[maxl + 1][10];
		f[0][0] = 1;
		g = new int[maxl + 1][10];
		g[0][0] = 1;
	}
	static void getd(int n) {
		digit = new int[maxl + 1];
		while (n > 0) {
			digit[++digit[0]] = n % 10;
			n /= 10;
		}
	}
	static int dfs(int d, int r, boolean c) {
		if (d == 0) {
			if (c)
				f[d + 1][r]++;
			return 0;
		}
		if (!(f[d + 1][r] > 0)) {
			int add = 0;
			int up = c ? 9 : digit[d];
			for (int i = 0; i <= up; i++)
				if (!(r == 6 && i == 2)) {
					if (!(f[d][i] > 0))
						dfs(d - 1, i, c || i != up);
					if (i != 4)
						add += f[d][i];
				}
			f[d + 1][r] += add;
		}
		int res = digit[d] == 4 || digit[d] == 2 && digit[d + 1] == 6 ? 0 : dfs(d - 1, 0, false);
		for (int i = 0; i < digit[d]; i++)
			if (i != 4 && !(i == 2 && digit[d + 1] == 6))
				res += f[d][i];
		return res;
	}
	static int solve(int n) {
		int res = 0;
		getd(n);
		return dfs(digit[0], 0, true);
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
		PrintWriter out = new PrintWriter(System.out);
		init();

		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			int n = (int) in.nval;
			in.nextToken();
			int m = (int) in.nval;
			if (n == 0 && m == 0)
				break;
			out.println(solve(m + 1) - solve(n));
		}
		out.flush();
		out.close();
	}
}

• 为何生成与统计分两步走？
  因为前i+1位的各种情况以前i位为依据生成，不能打断这个递推的连续性。
  待统计时再筛选所需。
• 为何solve(m+1)?
  便捷化处理，搜集<m+1的答案即≤m的答案。
• 为何这个记忆化搜索极易写挂？
  许多人根据数字的可选或不可选来划分状态，而此处为了清晰的体现数位的筛选辄以数字为状态。
  状态的更新与统计仍是分离的。