Brief description:
Level 3 又是一个关于堆砖的视图问题，感觉这类问题嘛、算法难度虽不高。。。
不过分析起来实非轻易，若不进行及时的总结，大概下次还是会落入 “重与漏” 的陷阱里。。。
今回题目是个二维版本，砖块分为 1×1 的彩色 cubes 和 1×2 的黑色 prisms，
。。|cubes| = n、 Sigma{cubes[..]} = s、黑砖数目为 B、宽度为 W 。。不要求摆放完。。
DIV 2 1050 SkewedPerspectives:
判定给定视图的合法性。（n ≤ 3、B ≤ 100、W ≤ 50 .. .）
DIV 1 1050 SkewedPerspective
对所有可能视图进行计数。（n ≤ 50、s ≤ 50、B ≤ 10、W ≤ 8 .. .）
.. . Remember from the division 2 explanation that whenever we move to a new column to place a prism, it creates empty space that must be filled. The empty space will be composed of two parts: fill1: This is the number of places that forcefully need cubes (remember that this happens when the empty space in a column is odd). We need it to know the number of remaining cubes. fill2: The number of spaces of size 1x2. Which we can eventually replace with a prism or 2 cubes each. ..
两个问题一起看是比较科学的，要解决计数问题大概至少要理解判定版本的问题，解决判定问题是注意到上面的话。。
大概的含义如图所示，总是就是要尽量本着用料节省的原则。
…
.. .
const int MOD = 1000000007;
const int INF = 0x7fffffff;
const int N = 50;
int cubes[3], B, W;
bool check(string view){
int h = SZ(view), b = B, w = W - 1, c[3]; CPY(c, cubes);
int f0 = 0, f1 = 0;
if (view[0] == 'b' && (SZ(view) == 1 || view[1] != 'b')) return false;
REP(i, h) if (view[i] == 'b'){
int _i = i++;
while (i < SZ(view) && view[i] == 'b') ++i;
int len = (i--) - _i;
b -= (len + 1) / 2;
if (len&1){
--w, f0 += abs(_i - 1);
if ((_i-1)&1) ++f1;
}
}
else{
--c[view[i]-'0'];
}
if (c[0] < 0 || c[1] < 0 || c[2] < 0 || b < 0 || w < 0) return false;
int s = c[0] + c[1] + c[2];
if (s < f1 || s + b*2 < f0) return false;
return true;
}
class SkewedPerspectives {
public:
vector <string> areTheyPossible(vector <int> _cubes, int _B, int _W, vector <string> views) {
B = _B, W = _W; cubes[0] = _cubes[0], cubes[1] = _cubes[1], cubes[2] = _cubes[2];
vector<string> res; REP(i, SZ(views)) res.PB(check(views[i]) ? "valid" : "invalid");
return res;
}
};
对于判定版本的问题，将 Cubes 当做整体来处理还可做可不做的话，但是计数版本就不能退让了。
先用动态规划和二项式系数做出辅助数组 G。
G[i]: 从所有 Cubes 中，选出 i 个排成一行，颜色不同的方法数。
。。最大的难点是抽象出接下来要推的状态。。。
首先已经定义使用的 Cubes 数为 nn、
出现的单格的黑砖数为 b1（仅在此情况下需要切行）、
双格黑砖数为 b2 。。
接下来考虑填坑的问题。。。
f0: 需要填的坑的总数。 f1: 其中必须用 cubes 填的坑。 f2: 其中可以用 prisms 填的坑。
。。知二求三，节省起见就存 f1、f2（.. .f1 < W .. . 2f2 ≤ 2B + n .. .）。。。 此外同判定问题一样这里仍然需要考虑摆放 b1 时的限制问题、需要加一维状态描述最后填的是否是黑砖。(bool bk)。。。 于是总的状态就是：
…
const int N = 50, BB = 10, WW = 8;
.. .
int F[N+1][WW][BB+1][WW][N/2+BB+1][2];
.. .
const int Null = -1;
int f(int nn = 0, int b1 = 0, int b2 = 0, int f1 = 0, int f2 = 0, bool bk = false){
int &res = F[nn][b1][b2][f1][f2][bk];
while (res == Null){
.. .
}
return res;
}
最后状态转移转移分 nn+1、b1+1、b2+1 三种情况讨论即可。。。。
const int N = 50, BB = 10, WW = 8;
int B, W; VI cubes;
int F[N+1][WW][BB+1][WW][N/2+BB+1][2], G[N+1], C[N+1][N+1], tmp[N+1][N+1];
int n, s;
const int Null = -1;
int f(int nn = 0, int b1 = 0, int b2 = 0, int f1 = 0, int f2 = 0, bool bk = false){
int &res = F[nn][b1][b2][f1][f2][bk];
while (res == Null){
res = 0; int rs = s-nn-f1, rb = B-b1-b2;
if (rb < 0 || rs < 0 || b1 >= W || rs/2 + rb < f2) break;
int h = nn + b1 + 2*b2;
if (h) INC(res, G[nn]);
if (rs) INC(res, f(nn+1, b1, b2, f1, f2, false));
if (rb){
INC(res, f(nn, b1, b2+1, f1, f2, true));
if (h&&(!bk||h==2&&b2==1)) INC(res, f(nn, b1+1, b2, f1+((h-1)&1), f2+(h-1)/2, true));
}
}
return res;
}
class SkewedPerspective{
public:
int countThem(vector <int> _cubes, int _B, int _W){
B = _B, W = _W, cubes = _cubes, n = SZ(cubes), s = accumulate(ALL(cubes), 0);
RST(C); FOR_1(i, 0, s){C[i][0] = 1; REP_1(j, i) C[i][j] = sum(C[i-1][j-1], C[i-1][j]);}
RST(tmp); tmp[0][0] = 1; REP_1(i, n) FOR_1(j, 0, s) FOR_1_C(k, 0, min(cubes[i-1], j)) INC(tmp[i][j], pdt(C[j][k], tmp[i-1][j-k]));
CPY(G, tmp[n]); FLC(F, Null);
return f();
}
};
