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

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?

Solution

这个问题可以使用动态规划(Dynamic programming)的思想来求解,我们用下式来表示满足条件的 prize strings的数量: $$ PS(D,A,L) $$ 其中$D$表示考勤的天数, $A$表示**恰在序列尾部**Absent 的天数,$L$表示**整个序列**中Late 的天数。 由题意可知 ,满足条件的第$D$天可以在第$D-1$天的基础上分情况考虑: - 当第$D$天是 On time 时,第$D-1$天满足条件的序列为:$$PS(D-1,A,L) $$ - 当第$D$天是 Late 时,第$D-1$天满足条件的序列为:$$PS(D-1,A,L-1)$$ - 当第$D$ 天是Absent 时,第$D-1$ 天需满足条件的序列为: $$PS(D-1,A-1,L)$$ 所以,结合初始条件我们可以得到: - 当$D=0$ 时,初始令 $$ PS(D,A,L) =PS(0,0,0) =1 $$ - 当$D=1$时,有 $$ PS(D,A,L) =PS(1,0,0) +PS(1,1,0) +PS(1,0,1) =3 $$ - 当$D>1$时,有 $$ PS(D,A,L)=PS(D-1,A,L)+PS(D-1,A,L-1)+PS(D-1,A-1,L) $$ 因此,通过编写动态规划的代码就可以对问题迭代求解,从而得到满足题目要求的Prize Strings。

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