【动态规划】【记忆化搜索】hdu5965 扫雷
2024-10-21 09:19:35
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);
}
}
最新文章
- 使用jstack分析cpu消耗过高的问题
- API -- java.lang.Integer
- ItextDemo<二>
- Ubuntu下安装配置JDK1.7
- 1029-c语言文法的理解
- 文件管理php代码操作文件
- 如何使用SQL Server链接服务器访问DB2 Server
- utmp, wtmp, and lastlog 日志清除工具
- Storm学习笔记六
- 【附答案】Java 大数据方向面试题，你会几个？
- PHP大文件分割上传（分片上传）
- selenium提供的截图功能
- ArcMap中获取要素的Extent值
- 关于AJAX异步请求
- Windows启动过程(MBR引导过程分析)
- cacti 流量图合并
- spring的设计模式
- C++ is_same
- 自学Python3.2-函数分类（内置函数）
- STM32外设地址查询