当前位置: 首页 > 工具软件 > Puzzle Game > 使用案例 >

HDU&icpc15沈阳 Matches Puzzle Game(数位)

暴向笛
2023-12-01

Matches Puzzle Game

这题不难的…还是自己太菜了

看完后觉得还是很巧妙的.

a-b=c不好判断,变形为a=b+c

所以从低位到高位枚举b,c的取值进行DP

第 一 步 设 计 状 态 \color{Red}第一步设计状态

首 先 肯 定 要 保 存 当 前 剩 下 几 根 火 柴 , 还 要 处 理 当 前 是 否 有 进 位 首先肯定要保存当前剩下几根火柴,还要处理当前是否有进位 ,

然 后 . . . . . 还 要 保 存 b 和 c 是 否 枚 举 完 毕 ! ! 然后.....还要保存b和c是否枚举完毕!! .....bc!!

为 什 么 有 这 一 维 信 息 ? 因 为 如 果 枚 举 完 毕 , 选 数 字 0 的 代 价 就 是 0 了 ! ! ( 不 花 费 火 柴 ) 为什么有这一维信息?因为如果枚举完毕,选数字0的代价就是0了!!(不花费火柴) ?,00!!()

所 以 定 义 d p [ u s e ] [ f 1 ] [ f 2 ] [ f l o w ] 表 示 还 剩 u s e 根 火 柴 所以定义dp[use][f1][f2][flow]表示还剩use根火柴 dp[use][f1][f2][flow]use

f 1 , f 2 表 示 是 否 枚 举 完 毕 , f l o w 表 示 是 否 有 进 位 f1,f2表示是否枚举完毕,flow表示是否有进位 f1,f2,flow

然后数位DP就几行代码…是不过因为 f 1 , f 2 f1,f2 f1,f2需要分情况而已

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,mod,t;
int a[20]={6,2,5,5,4,5,6,3,7,6};
int dp[509][2][2][2];//枚举到第i位还剩j根火柴 
int dfs(int use,int f1,int f2,int flow)
{
	if( use<0 )	return 0;
	int &now=dp[use][f1][f2][flow];
	if( now!=-1 )	return now;
	if( f1&&f2 )	return flow*2==use;//进位,需要2根火柴 
	now=0;
	if( !f1&&f2 )//f2枚举完毕 
	{
		for(int i=0;i<=9;i++)
		{
			int cost=a[i]+a[(i+flow)%10];
			now+=dfs( use-cost,f1,f2,(i+flow)/10)%mod;
			if( i )	now+=dfs( use-cost,1,f2,(i+flow)/10)%mod;//最高位不是0,那么可以结束了 
		}
	}
	else if( f1&&!f2 )
	{
		for(int i=0;i<=9;i++)
		{
			int cost=a[i]+a[(i+flow)%10];
			now+=dfs( use-cost,f1,f2,(i+flow)/10)%mod;
			if( i )	now+=dfs( use-cost,f1,1,(i+flow)/10)%mod;
		}		
	}
	else
	{
		for(int i=0;i<=9;i++)
		for(int j=0;j<=9;j++)
		{
			int cost=a[i]+a[j]+a[(i+j+flow)%10];
			now+=dfs( use-cost,f1,f2,(i+j+flow)/10 );
			if( i )	now+=dfs( use-cost,1,f2,(i+j+flow)/10 );
			if( j )	now+=dfs( use-cost,f1,1,(i+j+flow)/10 );
			if( i&&j )	now+=dfs( use-cost,1,1,(i+j+flow)/10 );
		}
	}
	return now%=mod;
} 
signed main()
{
	cin >> t;
	int casenum=0;
	while( t-- )
	{
		cin >> n >> mod;
		memset(dp,-1,sizeof(dp));
		cout << "Case #" << ++casenum << ": " << dfs(n-3,0,0,0) << endl;
	}
}
 类似资料: