题解：CF413D 2048

题意简述：

给定长度为

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

全部选定的情况。

坑点：

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

代码公示：

CPP

#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)]; 
}

文章操作