SRM 564 div1

250pt

我真够250的。3*3的棋盘跟4*4的棋盘搞混了。3*3正好是一个特例，结果为8，。。。。然后被cha掉了。。

class KnightCircuit2 {
public:
    int maxSize(int w, int h) {
        if(w > h)    swap(w, h);
        if(w == 1)    return 1;
        else if(w == 3 && h == 3)    return 8;
        else if(w == 2)    return h/2 + (h%2 != 0);
        else        return w*h;
    }
};

500pt

dp，比赛的时候推数论没有推出来。。。n*3*3*3的朴素dp不加任何优化都能过掉。。。

dp[i][x][y][z]表示第i个位置为颜色z，i-1位置为y，i-2位置为x。

如果y == z，那么i+1位置颜色只能是z，不然也不会出现两个连续的z颜色

如果x == z，下一个状态可以是yzy, yzx, yzz，又yzx == yzz所以只统计一个状态就行。

如果x y z互不相等，下一个状态可以是yzx, yzy, yzz...

初始状态满足:z = 0, x != y, y != z, x != z. f[1][x][y][0] = 1;

LL f[100010][3][3][3];

class AlternateColors2 {
public:
    long long countWays(int n, int k) {
        CL(f, 0);

        int x, y, z, i;
        f[1][2][1][0] = 1;

        for(i = 2; i <= n; ++i) {
            for(x = 0; x < 3; ++x) {
                for(y = 0; y < 3; ++y) {
                    for(z = 0; z < 3; ++z) {
                        if(f[i-1][x][y][z] == 0)    continue;
                        if(i - 1 == k && z != 0)    {f[i-1][x][y][z] = 0; continue;}
                        if(y == z) {
                            f[i][y][z][z] += f[i-1][x][y][z];
                        } else if(x == z) {

                            f[i][y][z][x] += f[i-1][x][y][z];
                            f[i][y][z][y] += f[i-1][x][y][z];
                        } else if(x != z && x != y && y != z) {
                            f[i][y][z][x] += f[i-1][x][y][z];
                            f[i][y][z][y] += f[i-1][x][y][z];
                            f[i][y][z][z] += f[i-1][x][y][z];
                        }
                    }
                }
            }
        }
        LL ans = 0;
        for(x = 0; x < 3; ++x) {
            for(y = 0; y < 3; ++y) {
                for(z = 0; z < 3; ++z) {
                    if(k == n && z != 0)    continue;
                    ans += f[n][x][y][z];
                }
            }
        }
        return ans;
    }
};