某島

… : "…アッカリ~ン . .. . " .. .
March 14, 2020

SRM 671

250

數據範圍很小,暴力 DP 吧。

const int N = 200 + 9;
int f[2][N][N], (*f0)[N], (*f1)[N];

class BearCries {
public:
	int count(string message) {

	    int n = SZ(message); f0 = f[0], f1 = f[1];
	    REP(i, n) REP(j, n) f1[i][j] = 0; f1[0][0] = 1;

	    REP(i, n) {
	        char c = message[i];
	        swap(f0, f1); REP(i, n) REP(j, n) f1[i][j] = 0;
#define u f0[i][j]
	        REP(i, n) REP(j, n) if (u){
                if (c == ';') {
                    f1[i+1][j] += u;
                    if (j) f1[i][j-1] += u*j;
                } else {
                    if (i) f1[i-1][j+1] += u*i;
                    f1[i][j] += u*j;
                }
	        }
	    }

		return f1[0][0];
	}
};

500

… 形式有點像叉積,感覺可以極角排序。
不過 Tourist 的代碼非常精妙,使用了 gcd 存放斜率,避免了叉積,然後第二關鍵字為右邊端點,第三關鍵字讓右端點置為 -1 ,巧妙的避免了重複計數。

900

const int N = 14;
typedef pair<Int,Int> pii;
pii f[2][1<<N], *f0, *f1, u;
// ways, score
int s, i, j, W, H;

void put(pii& v, int t) {
    v.fi += u.fi;
    v.se += u.fi*t + u.se;
}

void skip() {
    put(f1[s&~_1(i+1)], 0);
}

bool putRight() {
    if (j == W-1 || _1(s, i) || _1(s, i+1)) return 0;
    put(f1[s|_1(i)], 1);
    return 1;
}

bool putDown() {
    if (i == H-1 || _1(s, i+1)) return 0;
    put(f1[s|_1(i+1)], 1);
    return 1;
}

class BearDestroys {
public:
	int sumUp(int W, int H, int MOD) {
        ::MOD = MOD; ::W = W; ::H = H; f0 = f[0], f1 = f[1]; int S = 1<<H+1;
        REP(s, S) f1[s] = {0,0}; f1[0] = {1,0};

        REP(ij, W+H-1) {
            int il = max(0, ij-W+1), ir = min(H, ij+1);
            FOR_N(i, il, ir) {
                j = ij - i; swap(f0, f1); REP(s, S) f1[s] = {0, 0};
                REP_N(s, S) {
                    u = f0[s];
                    if (!putRight() && !putDown()) skip();
                    if (!putDown() && !putRight()) skip();
                }
            }
            swap(f0, f1); REP(s, S) f1[s] = {0, 0};
            REP(s, 1<<H) f1[s<<1] = f0[s];
        }
        //exit(0);

		return f1[0].se;
	}
};