网易雷火-游戏研发第五题
前面找规律找伤了,分享一下代码,希望好运到来🤣。
思路:
和状压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; }