网易雷火-游戏研发第五题
前面找规律找伤了，分享一下代码，希望好运到来🤣。
思路：
和状压dp类似，先预处理出所有状态，然后dp。
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 2e3 + 10;
int cnt=0;
int data[2000][32];
int dp_map[15][2000][32];
ll dp[15][2000];
int w,h;
int dfs(int x,int vis[32])
{
if(x==w)
{
for(int i=0;i<=30;i++)
{
data[cnt][i]=vis[i];
}
cnt++;
}
if(x>30)return 0;
vis[x+2]=1;
dfs(x+2,vis);
vis[x+2]=0;
vis[x+3]=1;
dfs(x+3,vis);
vis[x+3]=0;
return 0;
}
int main()
{
int ini[32];
memset(ini,0,sizeof ini);
cin>>w>>h;
if(w==3||w==2)
{
cout<<1<<endl;
return 0;
}
dfs(0,ini);
for(int i=0;i<cnt;i++)
{
dp[1][i]=1;
for(int j=0;j<31;j++)dp_map[1][i][j]=data[i][j];
}
for(int i=2;i<=h;i++)
{
for(int j=0;j<cnt;j++)
{
if(dp[i-1][j]==0)continue;
for(int k=0;k<cnt;k++)
{
int flag=0;
for(int p=0;p<w;p++)
{
if(dp_map[i-1][j][p]==data[k][p]&&data[k][p]==1)
{
flag=1;
break;
}
}
if(flag==0)
{
dp[i][k]+=dp[i-1][j];
for(int p=0;p<31;p++)
{
dp_map[i][k][p]=data[k][p];
}
}
}
}
}
ll ret=0;
for(int i=0;i<cnt;i++)
{
ret+=dp[h][i];
}
cout<<ret<<endl;
return 0;
}
