codevs3261 小明集邮票 (记忆化搜索)

2017年05月11日 12点热度 0人点赞 0条评论

3261 小明集邮票

 时间限制: 1 s
 空间限制: 256000 KB
 题目等级 : 黄金 Gold

题目描述 Description

小明是个喜欢集邮的孩纸,当然他对邮票的选择是非常严苛的。现在他获得了一次免费选择N张邮票的机会,选择的邮票会按照选择的顺序放入集邮册中。现在有五种邮票:金木水火土,分别作数字标记为1 2 3 4 5,他选择的邮票有以下规则要求,求有多少种选择的方式。
1)所有邮票必须都要选中;
2)必须有相邻的两个邮票(数字标记)差为3
3)只能选金木水火土五种邮票
4)N张邮票必须全部选完
5)N张邮票(数字标记)的和必须小于等于M
注意:选择排列的顺序不同算作两种方案。

输入描述 Input Description

一行,两个整数,分别为N和M

输出描述 Output Description

一行整数,表示集邮的方案选择总数。

样例输入 Sample Input

3 0

样例输出 Sample Output

0

数据范围及提示 Data Size & Hint

0<=N<=25 , 0<=M<=125  ,输出用longlong型整数

#include
#include
#include
using namespace std;
#define ll long long
int n,m;
ll dp[26][10][2][127][1<<5];
//dp[已选张数][上次取的邮票][是否有距离为3][数组和][每张是否被取到(二进制)];
ll dfs(int i,int be,bool flag,int sum,int now){
	//这个函数要return,不然不好统计和
	if(i>n||sum>m) return 0;//这个位置要放在最前面,防止爆空间 
	ll& t=dp[i][be][flag][sum][now];
	if(t) return t;
	if(i==n&&sum<=m&&flag&&now==31) return t=1;
	for(int ii=1;ii<6;ii++){//这个i容易和最开始的i搞混 
		if(abs(be-ii)==3)
		t+=dfs(i+1,ii,1,sum+ii,now|1<<(ii-1));
		else t+=dfs(i+1,ii,flag,sum+ii,now|1<<(ii-1));
	}
	return t;
}
int main(){
	scanf("%d%d",&n,&m);
	printf("%lldn",dfs(0,9,0,0,0));
	return 0;
}
未经允许不得转载!codevs3261 小明集邮票 (记忆化搜索)

update

纸上得来终觉浅, 绝知此事须躬行。