### 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)?

### 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