【數位DP】SPOJ BALNUM Balanced Numbers

通道：http://www.spoj.com/problems/BALNUM/

題意：求【A,B】區間内奇數出現了偶數次，偶數出現奇數次的數的個數

思路：3進制壓縮，0，1，2表示數字i出現了0次，1次，2次，dp[i][j][k]：前i位數位0～9出現的狀态為j時的個數，這裡的K代表是否包含了最高位非0，注意這裡的清空要放在case外面，畢竟之前算過的狀态就不要重複算了。

代碼：https://github.com/Mithril0rd/Rojo/blob/master/spojbalnum.cpp

TAG：3進制壓縮與數D

以下是優化後的JAVA代碼，其實就是加個預處理：

dp[i][j]：前i位0～9出現了0次，奇數次，偶數次。

import java.io.*;
import java.util.*;

public class Main {
	
	final static int MAX_D = 21;
	final static int MAX_N = 59057;
	
	int check[] = new int[MAX_N];
	long dp[][] = new long[MAX_D][MAX_N];
	int digit[] = new int[11], dig[] = new int[MAX_D];
	int p3[] = new int[11];
	
	int get(int x, int y) {
		int t = x / p3[y];
		if(t % 3 < 2) x += p3[y];
		if(t % 3 == 2) x -= p3[y];
		return x;
	}
	
	long dfs(int pos, int st, boolean limit) {
		if (0 == pos) return dp[pos][st] = check[st];
		if (!limit && -1 != dp[pos][st]) return dp[pos][st];
		int end = limit ? dig[pos] : 9;
		long ans = 0;
		for (int i = 0; i <= end; ++i) {
			boolean nxt = (st != 0) || (i != 0);
			ans += dfs(pos - 1, nxt ? get(st, i) : 0, limit && i == end);
		}
		if (!limit) dp[pos][st] = ans;
		return ans;
	}
	
	long cal(long x) {
		int n = 0;
		while (x > 0) {
			dig[++n] = (int) (x % 10);
			x /= 10;
		}
		return dfs(n, 0, true);
	}
	
	int F(int x) {
		int id = 0;
		while (x > 0) {
			int num = x % 3;
			if (num != 0) {
				if (num == 1 && (id & 1) != 0) return 0;
				else if (num == 2 && (id & 1) == 0) return 0;
			}
			x /= 3;
			++id;
		}
		return 1;
	}
	
	void run() throws IOException {
		for (int i = 0; i < MAX_N; ++i)
			check[i] = F(i);
		p3[0] = 1;
		for (int i = 1; i < 11; ++i) p3[i] = p3[i - 1] * 3;
		int T = cin.nextInt();
		for (int i = 0; i < MAX_D; ++i)
			Arrays.fill(dp[i], -1);
		while (T-- > 0) {
			long l = cin.nextLong();
			long r = cin.nextLong();
			long ans = cal(r) - cal(l - 1);
			out.println(ans);
		}
		out.close(); 
	}

	public static void main(String[] args) throws IOException {
		new Main().run();
	}

	Main() {
		 cin = new InputReader(System.in);
	//	cin = new Scanner(System.in);
		out = new PrintWriter(System.out);
	}

	PrintWriter out;
	InputReader cin;
	//Scanner cin;

	class InputReader {
		InputReader(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			// try {
			// reader = new BufferedReader(new FileReader("input.txt"));
			// } catch (FileNotFoundException ex) {
			// }
			tokenizer = new StringTokenizer("");
		}

		private String next() throws IOException {
			while (!tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}

		public Integer nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		private BufferedReader reader;
		private StringTokenizer tokenizer;
	}
}
           

　　

轉載于:https://www.cnblogs.com/Rojo/p/4066504.html