题解：CF413D 2048

FDOI · 2025-04-18 20:32:21 · 题解

题意简述：

给定长度为 n 的序列，将其进行 k 次操作，每次压入一个 2 或者 4，之后以题目中给定的游戏规则，即 2048 游戏规则进行合并，最后要求给出可行的方案数量，使得序列中的最大数大于 2^k。

思路分析：

看到这道题的 k 居然如此之小，再者要求方案数，优先想到状压。

接下来是保姆级的分析。

定义状态：

标准的方式，定义二维，表示压入前 i 个数后情况数为 j。

不熟悉状压的可以先去学板子。

初始化：

可以想到，当不压入时，这也是一种合法情况，这时令 dp_{0,0} 为 1 即可。

状态转移：

这是本题的关键所在，应该分两种不同的情况分析。

• 当压入的是 2 时，这时由于其是最小数，所以一定可以将其压入序列中，此时状态 j 就会加二，并且压入了 i+1 个数，此时如果已经满足最大值大于 2^k ，就直接继承 j 全部选定，即 j=2^k 的情况，否则就继承当前情况 j+2 即可。
• 反之，当压入的是 4 时，我们又要分类讨论，当此时的状态中，上一个数已经为 2 时，此时无法在上一个状态中直接压入 4，所以说此时直接继承 j=4 时的情况另开，当此时恰好满足 j+4=2^k 时，那么不用再继续更新，直接继承来自 j 的状态即可，否则如果不满足上述情况时，就同理要么已经大于 2^k 继承 j=2^k 的状态，要么就不满足不大于继承 j+4 的情况。

输出答案：

显然，输出当压入完 n 个数，状态为 2^k 全部选定的情况。

坑点：

• 记得取模。
• 数组一定要开够。
• 要仔细理解题意，注意细节错误。
• 千万不要抄题解。

代码公示：

#include<bits/stdc++.h>
using namespace std;
const int P=1e9+7;
int n,k;
int x;
int dp[2005][(1<<11)+1];
int a[3005];
signed main(){
    cin>>n>>k;
    dp[0][0]=1;
    for(int i=0;i<n;i++){
        cin>>x;
        for(int j=0;j<=(1<<k);j++){
            if(x!=4){
                int ni=i+1;
                int nj=min((1<<k),j+2);
                dp[ni][nj]=(dp[ni][nj]+dp[i][j])%P;
            }
            if(x!=2){
                int ni=i+1;
                int nj=j+4;
                if(nj==(1<<k)) nj=j;
                if(j&2){
                    nj=4;
                }
                else nj=min(j+4,(1<<k));
                dp[ni][nj]=(dp[ni][nj]+dp[i][j])%P;
            }
        }
    }
    cout<<dp[n][(1<<k)]; 
}