题解 CF413D 【2048】

skylee · 2018-05-03 20:42:29 · 题解

题解地址：

[CF413D]2048 - skylee's Blog

题目大意：

在一个长度为n(n\le2000)的数组中填数2或4，待所有数字全部填好后，按照类似于2048的规则向左合并。给定某些格子上的数，问在当前情况下要使得合并后的最大数超过2^k有几种填法。

思路：

动态规划。
定义一个状态为最长不上升后缀的数字和，如(16,4,8,4,4,2)对应的状态为18，因为后面这些还是有机会合并的，且合并的过程可以直接用加法代替，如(16,4,8,4,4,2)后面再加上一个2，对应的状态变为18+2=20。定义目标状态为2^k，超过这个的状态对其取\min。用f[i][j]表示前i个格子状态为j的方案数，则不难得到如下转移：

• 当x=2时，f[i][\min(j+2,2^k)]+=f[i-1][j]；
• 当x=4且当前最后有多余2时，新加进来的数不可能再和前面的合并了，故不将前面的计入状态，f[i][4]+=f[i-1][j]；
• 当x=4且当前最后无多余2时，f[i][\min(j+4,2^k)]+=f[i-1][j]。
• 当x不确定时，同时进行上述两种转移即可。

时间复杂度O(n\cdot2^k)。

源代码：

#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int K=10,mod=1e9+7;
int f[2][(1<<K)+1];
int main() {
    const int n=getint(),k=getint()-1;
    for(register int i=f[0][0]=1;i<=n;i++) {
        const int x=getint();
        std::fill(&f[i&1][0],&f[i&1][1<<k]+1,0);
        for(register int j=0;j<=1<<k;j++) {
            if(x!=2) (f[i&1][j&1?2:std::min(j+2,1<<k)]+=f[(i&1)^1][j])%=mod;
            if(x!=4) (f[i&1][std::min(j+1,1<<k)]+=f[(i&1)^1][j])%=mod;
        }
    }
    printf("%d\n",f[n&1][1<<k]);
    return 0;
}