Matches Puzzle Game
Problem DescriptionAs an exciting puzzle game for kids and girlfriends, the Matches Puzzle Game asks the player to find the number of possible equations A−B=C with exactly n (5≤n≤500) matches (or sticks).
In these equations, A,B and C are positive integers. The equality sign needs two matches and the sign of subtraction needs just one. Leading zeros are not allowed.
Please answer the number, modulo a given integer m (3≤m≤2×109).InputThe input contains several test cases. The first line of the input is a single integer t which is the number of test cases. Then t (1≤t≤30) test cases follow.Each test case contains one line with two integers n (5≤n≤500) and m (3≤m≤2×109).
OutputFor each test case, you should output the answer modulo m.Sample Input4
12 1000000007
17 1000000007
20 1000000007
147 1000000007Sample OutputCase #1: 1
Case #2: 5
Case #3: 38
Case #4: 815630825Source
【题意】
有n根火柴(n<=500)，要刚好用完，摆出一个减式A-B=C(A>0,B>0,C>0)求有多少种方案
【分析】
这题很好想，但是就看个人DP能力了，我一开始打的DP就TLE，真是太年轻！
之前做的几题数位DP都是数字限制，即数值固定一个区间，而现在这题可不管你那个数有多大，只要火柴够用就好了。
所以之前的题我是记录位数，标记前导0的，再加个越限标记flag。
搞到我这题一开始就也记录位数了，然记录位数并无卵用！！还会TLE啊ORZ，
我一开始想法，先减掉3根火柴，减法变加法（加法好打一些），f[i][j][k]表示i位，j根火柴，k表示状态（即两个加数分别是否还处于前导0中），然后记忆化搜索
位数不超过n/4的，所以时间大概是150*500*4*10*10*2，代码也放一下，正确性还是保证的：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define LL long long int f[][][][];//weishu huocai zero shifoujinwei
// 0 00 1 0x 2 x0 3 xx
int us[]={,,,,,,,,,};
int m,sum; int ffind(int n,int k,int zero,int step)
{
sum++;
if(k<) return ;
if(n==) return (k==&&step==);
if(f[n][k][zero][step]!=-) return f[n][k][zero][step];
LL ans=;
for(int a=;a<;a++)
for(int b=;b<;b++)
{
for(int l=;l<;l++) //xia yi bu shi fou jin wei
{
if(n==&&a==&&zero<=) continue;
if(n==&&b==&&zero!=&&zero!=) continue;
if(step&&(a+b+l<)) continue;
if(!step&&(a+b+l>=)) continue;
int now=;
if(a!=||zero==||zero==) now+=us[a];
if(b!=||zero==||zero==) now+=us[b];
if(a!=||b!=||l!=||zero!=) now+=us[(a+b+l)%];
if(now>k) continue; int nz;
if(a==&&b==&&zero==) nz=;
else if(a==&&zero!=&&zero!=) nz=;
else if(b==&&zero!=&&zero!=) nz=;
else nz=;
ans=(ans+ffind(n-,k-now,nz,l) )%m;
}
}
f[n][k][zero][step]=(int)ans;
return (int)ans;
} int main()
{
int T,kase=;
scanf("%d",&T);
while(T--)
{
sum=;
int n;
scanf("%d%d",&n,&m);
memset(f,-,sizeof(f));
printf("Case #%d: %d\n",++kase,ffind(n/,n,,));
}
return ;
}
TLE的代码
其实与位数无关，但是不及记录位数就要从低位开始填数了，不然无法表示，会重复。
f[j][k]表示j根火柴，k状态，状态表示当前两个加数分别是否结束了，结束了只能填0，并且不花费火柴。
AC代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define LL long long int f[][][];//weishu huocai zero shifoujinwei
// 0 00 1 0x 2 x0 3 xx
int us[]={,,,,,,,,,};
int m; int ffind(int k,int zero,int step)
{
if(k<) return ;
if(zero==)
{
if(step==) k-=;
return k==;
}
if(f[k][zero][step]!=-) return f[k][zero][step];
LL ans=;
for(int a=;a<;a++)
{
for(int b=;b<;b++)
{
int now=;
if(zero==||zero==) now+=us[a];
if(zero==||zero==) now+=us[b];
now+=us[(a+b+step)%];
if(now>k) continue; ans=(ans+ffind(k-now,zero,a+b+step>=) )%m;
if(a!=&&zero!=&&zero!=) ans=(ans+ffind(k-now,zero==?:,a+b+step>=) )%m;
if(b!=&&zero!=&&zero!=) ans=(ans+ffind(k-now,zero==?:,a+b+step>=) )%m;
if(a!=&&b!=&&zero==) ans=(ans+ffind(k-now,,a+b+step>=) )%m; if(zero==||zero==) break;
}
if(zero==||zero==) break;
} f[k][zero][step]=(int)ans;
return (int)ans;
} int main()
{
int T,kase=;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d%d",&n,&m);
memset(f,-,sizeof(f));
printf("Case #%d: %d\n",++kase,ffind(n,,));
}
return ;
}
[HDU 5456]
所以如果跟位数无关，最好思想回到原始的位置啊，从低位开始填可能会--柳暗花明又一村？？
2016-10-09 14:15:15