partialsolutions

C:

dp[i][st]:在第i列时,i-1列及之前已经全部填满,用方块将第i列状态填为st时的方案数。

dp[i][st0] -> dp[i+1][st1]:

首先要求st0中没有填的位置,st1必须填好,因为按照dp定义,我们必须填完之前所有方块,而我们仅有横着的2x1方块能填充之前一列。

剩下待填方块可能是几个分立的区间,需要用1x1,1x2填充。由乘法原理,先单独算每个区间的方案数,最后再乘起来。而单独一个区间的方案数则是婓波那契数列。

算出总方案数s(st0,st1)后,

dp[i+1][st1]=dp[i][st0]*s(st0,st1);

转移与i无关,将所有s(st0,st1)计算出后矩阵快速幂即可。

I:

将下去和上来看作两个人一起下去。

每层梯子数有限,设dp[s][i][j]:在第s层通过第i,j个楼梯下到第s+1层时,已经拿到的最大糖果数。

dp[s][i][j]->dp[s+1][ii][jj]

首先检查i,ii对应的区间与j,jj对应的区间是否存在交集,若存在交集,交集中是否有糖果,如果有糖果则直接continue,次为无效转移,因为有糖果的地方仅能路过一次,路径交叉则必然路过两次,不合题中限制。

如果上述条件符合,则可以转移。注意到每个区间的端点之外第一个糖果也可以拿,因为也仅需经过一次,碰到就可以回来了。注意两区间不要拿重了,可能有个糖果是两区间共同的边缘第一个。

计算答案时,枚举s : 2->n , i ,j
然后i,j直接拿完i,j区间以及i,j区间外第一个可拿糖果,用此更新ans.
注意s要枚举到n,因为最下层地板也是可以走的,可以多提供一条路径。