### Prize Strings题号：191 难度： 35 中英对照

A particular school offers cash rewards to children with good attendance and punctuality. If they are absent for three consecutive days or late on more than one occasion then they forfeit their prize.

During an n-day period a trinary string is formed for each child consisting of L's (late), O's (on time), and A's (absent).

Although there are eighty-one trinary strings for a 4-day period that can be formed, exactly forty-three strings would lead to a prize:

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA
LAOO LAOA LAAO

How many "prize" strings exist over a 30-day period?

### Code

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

private static final int NUM_DAYS = 30;
private static final int MAX_ABSENT = 2;
private static final int MAX_LATE = 1;

public static long run() {
// numPrizeStrings[i][j][k] is the number of prize strings of length i with
// exactly j absences at the tail and exactly k lates in the whole string
long[][][] numPrizeStrings = new long[NUM_DAYS + 1][MAX_ABSENT + 1][MAX_LATE + 1];
numPrizeStrings[0][0][0] = 1;
for (int i = 1; i <= NUM_DAYS; i++) {
for (int j = 0; j <= MAX_ABSENT; j++) {
for (int k = 0; k <= MAX_LATE; k++) {
// Count which states can be appended to the tail
long sum;
if (j == 0) {
sum = 0;
for (int l = 0; l <= MAX_ABSENT; l++)
sum += numPrizeStrings[i - 1][l][k];  // On time
if (k > 0) {
for (int l = 0; l <= MAX_ABSENT; l++)
sum += numPrizeStrings[i - 1][l][k - 1];  // Late
}
} else
sum = numPrizeStrings[i - 1][j - 1][k];  // Absent
numPrizeStrings[i][j][k] = sum;
}
}
}

long sum = 0;
for (int j = 0; j <= MAX_ABSENT; j++) {
for (int k = 0; k <= MAX_LATE; k++)
sum += numPrizeStrings[NUM_DAYS][j][k];
}
return sum;
}
}
1918080160
0ms