[CF413D]2048

题目大意：
　　在一个长度为$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^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int K=,mod=1e9+;

 int f[][(<<K)+];

 int main() {

     const int n=getint(),k=getint()-;

     for(register int i=f[][]=;i<=n;i++) {

         const int x=getint();

         std::fill(&f[i&][],&f[i&][<<k]+,);

         for(register int j=;j<=<<k;j++) {

             if(x!=) (f[i&][j&?:std::min(j+,<<k)]+=f[(i&)^][j])%=mod;

             if(x!=) (f[i&][std::min(j+,<<k)]+=f[(i&)^][j])%=mod;

         }

     }

     printf("%d\n",f[n&][<<k]);

     return ;

 }

Min

[CF413D]2048