- https://competitiveprogramming.info/topcoder/srm/round/16551/div/1
- user.qzone.qq.com/251815992/blog/1444839459

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