首页 > 代码库 > 【动态规划】【记忆化搜索】hdu5965 扫雷
【动态规划】【记忆化搜索】hdu5965 扫雷
f(i,j,k)表示第i行，放的雷的状态为j{0表示不放，1表示往上放，2表示往下放，3表示上下都放}，剩余还有k(0<=k<=2)个要放的方案数。
先给出我这个sb写的错误代码，死都没调出来。优越的做法在后面
#include<cstdio>
#include<cstring>
using namespace std;
#define MOD 100000007
int T,n;
char a[10010];
int f[10010][4][10];
int main(){
scanf("%d",&T);
for(;T;--T){
scanf("%s",a+1);
n=strlen(a+1);
a[0]=‘0‘;
memset(f,0,sizeof(f));
f[1][0][a[1]-‘0‘]=1;
if(a[1]-‘0‘-1>=0){
f[1][1][a[1]-‘0‘-1]=1;
}
if(a[1]-‘0‘-1>=0){
f[1][2][a[1]-‘0‘-1]=1;
}
if(a[1]-‘0‘-2>=0){
f[1][3][a[1]-‘0‘-2]=1;
}
for(int i=1;i<n;++i){
for(int j=a[i]-‘0‘;j>=a[i]-‘0‘-2 && j>=0;--j){
if(j<=2 && j+0<=a[i+1]-‘0‘){
if(j==0){
f[i+1][0][a[i+1]-‘0‘]=(f[i+1][0][a[i+1]-‘0‘]+f[i][0][0])%MOD;
}
else if(j==1){
f[i+1][1][a[i+1]-‘0‘-1]=(f[i+1][1][a[i+1]-‘0‘-1]+f[i][0][1])%MOD;
f[i+1][2][a[i+1]-‘0‘-1]=(f[i+1][2][a[i+1]-‘0‘-1]+f[i][0][1])%MOD;
}
else{
f[i+1][3][a[i+1]-‘0‘-2]=(f[i+1][3][a[i+1]-‘0‘-2]+f[i][0][2])%MOD;
}
}
}
for(int j=a[i]-‘0‘-1;j>=a[i]-‘0‘-2-1 && j>=0;--j){
if(j<=2 && j+1<=a[i+1]-‘0‘){
if(j==0){
f[i+1][0][a[i+1]-‘0‘-1]=(f[i+1][0][a[i+1]-‘0‘-1]+f[i][1][0])%MOD;
}
else if(j==1){
f[i+1][1][a[i+1]-‘0‘-2]=(f[i+1][1][a[i+1]-‘0‘-2]+f[i][1][1])%MOD;
f[i+1][2][a[i+1]-‘0‘-2]=(f[i+1][2][a[i+1]-‘0‘-2]+f[i][1][1])%MOD;
}
else{
f[i+1][3][a[i+1]-‘0‘-3]=(f[i+1][3][a[i+1]-‘0‘-3]+f[i][1][2])%MOD;
}
}
}
for(int j=a[i]-‘0‘-1;j>=a[i]-‘0‘-2-1 && j>=0;--j){
if(j<=2 && j+1<=a[i+1]-‘0‘){
if(j==0){
f[i+1][0][a[i+1]-‘0‘-1]=(f[i+1][0][a[i+1]-‘0‘-1]+f[i][2][0])%MOD;
}
else if(j==1){
f[i+1][1][a[i+1]-‘0‘-2]=(f[i+1][1][a[i+1]-‘0‘-2]+f[i][2][1])%MOD;
f[i+1][2][a[i+1]-‘0‘-2]=(f[i+1][2][a[i+1]-‘0‘-2]+f[i][2][1])%MOD;
}
else{
f[i+1][3][a[i+1]-‘0‘-3]=(f[i+1][3][a[i+1]-‘0‘-3]+f[i][2][2])%MOD;
}
}
}
for(int j=a[i]-‘0‘-2;j>=a[i]-‘0‘-2-2 && j>=0;--j){
if(j<=2 && j+2<=a[i+1]-‘0‘){
if(j==0){
f[i+1][0][a[i+1]-‘0‘-2]=(f[i+1][0][a[i+1]-‘0‘-2]+f[i][3][0])%MOD;
}
else if(j==1){
f[i+1][1][a[i+1]-‘0‘-3]=(f[i+1][1][a[i+1]-‘0‘-3]+f[i][3][1])%MOD;
f[i+1][2][a[i+1]-‘0‘-3]=(f[i+1][2][a[i+1]-‘0‘-3]+f[i][3][1])%MOD;
}
else{
f[i+1][3][a[i+1]-‘0‘-4]=(f[i+1][3][a[i+1]-‘0‘-4]+f[i][3][2])%MOD;
}
}
}
}
printf("%d\n",f[n][0][0]+f[n][1][0]+f[n][2][0]+f[n][3][0]);
}
return 0;
}
然后是斓爷优越的记忆化搜索
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
long long use[11000][3][3],dp[11000][3][3],qw,wq,l;
char s[11000];
long long mo=100000007;
long long num[3]={1,2,1};
long long getans(long long d,long long a,long long b)
{
if (d>l)
{
if (b!=0) return 0;
return 1;
}
if (b>2 || a+b>s[d-1]-48) return 0;
if (use[d][a][b]==qw) return dp[d][a][b];
use[d][a][b]=qw;
dp[d][a][b]=getans(d+1,b,s[d-1]-48-a-b)*num[b]%mo;
return dp[d][a][b];
}
int main()
{
scanf("%lld",&wq);
for (qw=1;qw<=wq;qw++)
{
scanf("%s",&s);
l=strlen(s);
printf("%lld\n",(getans(1,0,0)+getans(1,0,1)+getans(1,0,2))%mo);
}
}
【动态规划】【记忆化搜索】hdu5965 扫雷
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。