首页 > 代码库 > Coder-Strike 2014 - Round2 D 2048 (DP 记忆化搜索)

Coder-Strike 2014 - Round2 D 2048 (DP 记忆化搜索)

参考了  http://blog.csdn.net/keshuai19940722/article/details/24723417  他的开头的一点小分析,当然还有题意啦,难得看到CF的题目有点长,看了好久加YY才弄出题意,

但是还是没有推出来状态转移方程,因为题目说向开头移动,我倒着推没有推出来,于是 正着尝试了一把 记忆化搜索,一路搜索过来遇到的只有0,2,4而已,扫到当前一格 还得考虑当前状态的最后一位是否与当前这一位的能够合并,题目要求只有相同的值能合并,这里有一个小技巧,代码里注释了,

dp[id][now][mark]  代表 当前 第id个  前(id -1个的)和为now 以及前面是否出现了 now > 2 ^k 的情况 



#define MOD 1000000007

int n,k;

int nnum[2000 + 55];

int dp[2000 + 55][8000 + 55][2];

int Win;

void init() {
	memset(nnum,0,sizeof(nnum));
	memset(dp,-1,sizeof(dp));
}

bool input() {
	while(cin>>n>>k) {
		for(int i=0;i<n;i++)scanf("%d",&nnum[i]);
		return false;
	}
	return true;
}

int dfs(int id,int now,int mark) {
	if(now >= Win)mark = 1;
	if(dp[id][now][mark] != -1)return dp[id][now][mark];
	dp[id][now][mark] = 0;
	if(id == n) return dp[id][now][mark] = mark;
	if(nnum[id] == 0) {
		dp[id][now][mark] = (dp[id][now][mark] + dfs(id + 1,now + 2,mark))%MOD;
		if(now%4) dp[id][now][mark] = (dp[id][now][mark] + dfs(id + 1,4,mark))%MOD;
		/*这里%4的意思是:由于前面全都有2,4构成,所以能合并成为和为now的状态,那么前面的除却最后一位2,4肯定相互匹配了,
		现在对4取模,那么余数肯定为0或者2,若为2则表示构成当前和为now的最后一个数字为2,最后一个为2那么与接下来的4无法合并,now重新取和
		若为0,那么当前和now+2,而再下一步中,余数肯定为2了,所以又限定了只能取2不能取4,例如序列4 4 4 2,那么下一步肯定是只能取2才能合并,而且当前%4的值为2,
		而且由于2^k,k>=3,所以不会构成某个和now 刚好与 1<<K差了2,导致加了2使得答案多1   */
		else dp[id][now][mark] = (dp[id][now][mark] + dfs(id + 1,now + 4,mark))%MOD;
	}
	else {
		if(nnum[id] == 2) dp[id][now][mark] = (dp[id][now][mark] + dfs(id + 1,now + 2,mark))%MOD;
		else {
			if(now%4) dp[id][now][mark] = (dp[id][now][mark] + dfs(id + 1,4,mark))%MOD;
			else dp[id][now][mark] = (dp[id][now][mark] + dfs(id + 1,now + 4,mark))%MOD;
		}
	}
	return dp[id][now][mark];
}

void cal() {
	Win = 1<<k;
	int ans = dfs(0,0,0);
	cout<<ans<<endl;
}

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}

/*

6 4 
4 4 4 4 2 2

6 4 
4 4 4 4 2 0

ans :
1
2


*/


Coder-Strike 2014 - Round2 D 2048 (DP 记忆化搜索)