当前位置:首页 » Project Euler » 详细页

Exploring strings for which only one character comes lexicographically after its neighbour to the left 题号:158 难度: 55 中英对照

Taking three different letters from the 26 letters of the alphabet, character strings of length three can be formed.
Examples are 'abc', 'hat' and 'zyx'.
When we study these three examples we see that for 'abc' two characters come lexicographically after its neighbour to the left.
For 'hat' there is exactly one character that comes lexicographically after its neighbour to the left. For 'zyx' there are zero characters that come lexicographically after its neighbour to the left.
In all there are 10400 strings of length 3 for which exactly one character comes lexicographically after its neighbour to the left.

We now consider strings of n ≤ 26 different characters from the alphabet.
For every n, p(n) is the number of strings of length n for which exactly one character comes lexicographically after its neighbour to the left.

What is the maximum value of p(n)?

Solution

按数位动态规划(数位dp),需要用map进行记忆化。 用一个函数numWays来模拟数位dp的dfs(深度优先搜索)过程: numWays(i,j,k,bool)表示已经填入了k个字符,最后填入的字符是x,在字符集中比x小的字符有i个,比x大的有j个,bool表示当前的状态,若bool为true表示填入的字符还没有满足“存在一个字符与其前一个字符构成升序排列”,若为false表示已经满足上述条件,继续填字符时只能填入比当前字符x小的字符。 枚举第一位填入的字符,把调用numWays得到的答案全部加和得到字符集为n时的答案。 比较n从1到26的答案,取最大值即可。

Code

import java.util.TreeMap;

public final class p158 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }

	static TreeMap<Key, Long> map = new TreeMap<Key, Long>();
	
    static public String run() {
		long max = 0;
		for (int i = 1; i <= 26; i++) {
			if (p(i) > max) {
				max = p(i);
			}
		}
		return max+"";
    }
	public static long p(int n) {

		long sum = 0;
		for (int i = 1; i <= 26; i++) {
			sum += numWays(i - 1, 26 - i, n - 1, true);
		}
		return sum;
	}

	public static long numWays(int numLessThanLast, int numsGreaterThanLast,
			int numsLeft, boolean canPickGreater) {

		Key k = new Key(numLessThanLast, numsGreaterThanLast, numsLeft,
				canPickGreater);
		if (map.containsKey(k))
			return map.get(k);

		if (numLessThanLast < 0 || numsGreaterThanLast < 0)
			return 0;

		if (numsLeft == 0) {
			if (canPickGreater)
				return 0;
			return 1;
		}

		long sum = 0;

		for (int i = 1; i <= numLessThanLast; i++) {
			sum += numWays(i - 1, numLessThanLast - i + numsGreaterThanLast,
					numsLeft - 1, canPickGreater);
		}

		if (canPickGreater) {
			for (int i = 1; i <= numsGreaterThanLast; i++) {
				sum += numWays(i - 1 + numLessThanLast,
						numsGreaterThanLast - i, numsLeft - 1, false);
			}
		}

		map.put(k, sum);
		return sum;
	}
}

class Key implements Comparable<Key> {
	private int less, more, left;
	private boolean canPick;

	public Key(int l, int m, int le, boolean c) {
		less = l;
		more = m;
		left = le;
		canPick = c;
	}

	public int compareTo(Key other) {
		if (less == other.less) {
			if (more == other.more) {
				if (left == other.left) {
					if (canPick == other.canPick)
						return 0;
					else if (canPick)
						return 1;
					else
						return -1;
				}
				return left - other.left;
			}
			return more - other.more;
		}
		return less - other.less;
	}

}
409511334375
87ms