漳州最专业的网站建设,公司网站建设工作方案,重庆哪家做网站,seo海外先看几道比较简单的题#xff1a; 直接f[i][j]f[i-1][j]f[i][j-1]即可#xff08;注意有马的地方赋值为0#xff09;
下面是递推循环方式实现的AC代码#xff1a;
#includebits/stdc.h
using namespace std;
#define int long long
int a[30][30];
int n,m,x,y;
…先看几道比较简单的题 直接f[i][j]f[i-1][j]f[i][j-1]即可注意有马的地方赋值为0
下面是递推循环方式实现的AC代码
#includebits/stdc.h
using namespace std;
#define int long long
int a[30][30];
int n,m,x,y;
signed main(){cinnmxy;x;y;m;n;a[1][1]1;for(int i1;in;i){for(int j1;jm;j){if((abs(x-i)1abs(y-j)2)||(abs(x-i)2abs(y-j)1)||(xiyj)){a[i][j]0;continue;}if(i1j1) continue;a[i][j]a[i][j-1]a[i-1][j];}}couta[n][m];
}
下面是记忆化数组实现的AC代码
#includebits/stdc.h
using namespace std;
#define int long long
int a[30][30];
int n,m,x,y;
int dir[8][2]{{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
int dp(int x,int y){if(x0||xn||ym||y0) return 0;if(a[x][y]!-1) return a[x][y];return a[x][y]dp(x-1,y)dp(x,y-1);
}
signed main(){cinnmxy;x;y;n;m;memset(a,-1,sizeof(a));a[1][1]1;a[x][y]0;for(int i0;i8;i){int xxxdir[i][0];int yyydir[i][1];if(xx0||xxn||yym||yy0) continue;a[xx][yy]0;}coutdp(n,m);
}
接题 我们定义f[i][j]为第j同学的方案数注意n位同学旁边为1号与n-1)
下面是递推循环方式实现的AC代码
#includebits/stdc.h
using namespace std;
#define int long long
int n,m;
int dp[40][40];
signed main(){cinnm;dp[1][0]1;for(int i1;im;i){for(int j1;jn;j){if(j1){dp[j][i]dp[n][i-1]dp[j1][i-1];}else if(jn){dp[j][i]dp[j-1][i-1]dp[1][i-1];}else{dp[j][i]dp[j-1][i-1]dp[j1][i-1];}}}coutdp[1][m];
}
下面是用记忆化搜索的实现代码
#includebits/stdc.h
using namespace std;
#define int long long
int n,m;
int dp[40][40];
int f(int x,int y){if(y0) return 0;if(dp[x][y]!-1) return dp[x][y];if(x1) return dp[x][y]f(n,y-1)f(x1,y-1);if(xn) return dp[x][y]f(x-1,y-1)f(1,y-1);return dp[x][y]f(x-1,y-1)f(x1,y-1);
}
signed main(){cinnm;memset(dp,-1,sizeof(dp));dp[1][0]1;for(int i2;in;i) dp[i][0]0;coutf(1,m);
}
注意在用记忆化搜索时memset语句是必要的如果不加那么dp[x][y]!0时返回但事实上我们有很多地方值为0意味这退出情况大多是y0在起作用因此记忆化的作用发挥不出来虽然答案对但是运行很慢。
