(以“分类:棋盘动态规划 ==摘要== {{信息题|骑士游历|http://www.codevs.cn/problem/1219/|1|100|time=2014/11/28 20:21:12|50|边界问题}} ==题意== 在n...”为内容创建页面) |
小 (格式) |
||
(未显示1个用户的1个中间版本) | |||
第1行: | 第1行: | ||
[[分类:棋盘动态规划]] | [[分类:棋盘动态规划]] | ||
==摘要== | ==摘要== | ||
− | {{信息题|骑士游历|http://www.codevs.cn/problem/1219/|1|100|time=2014/11/28 20:21:12 | + | {{信息题|骑士游历|http://www.codevs.cn/problem/1219/|1|100|time=2014/11/28 20:21:12|边界问题|50}} |
==题意== | ==题意== | ||
在n*m的棋盘上,马只能从向右走日字格,求(x1,y1)到(x2,y2)的方案数。 | 在n*m的棋盘上,马只能从向右走日字格,求(x1,y1)到(x2,y2)的方案数。 | ||
第7行: | 第7行: | ||
*还是很简单的棋盘动态规划了,还是注意边界问题,这题是从1开始的Σ( ° △ °|||)︴ | *还是很简单的棋盘动态规划了,还是注意边界问题,这题是从1开始的Σ( ° △ °|||)︴ | ||
<pre> | <pre> | ||
+ | dp[x][y]=dp[x][y]+dp[x-1][y-2]+dp[x-1][y+2]+dp[x-2][y-1]+dp[x-2][y+1]; | ||
</pre> | </pre> | ||
+ | *本题需要用64位整数,无需高精度 | ||
==代码== | ==代码== | ||
{{折叠|1219.cpp代码已折叠 | {{折叠|1219.cpp代码已折叠 | ||
第22行: | 第24行: | ||
{ | { | ||
if(x>=2&&y>=3) | if(x>=2&&y>=3) | ||
− | dp[x][y]= | + | dp[x][y]=dp[x-1][y-2]; |
if(x>=2) | if(x>=2) | ||
− | + | dp[x][y]+=dp[x-1][y+2]; | |
if(x>=3&&y>=2) | if(x>=3&&y>=2) | ||
− | + | dp[x][y]+=dp[x-2][y-1]; | |
if(x>=3) | if(x>=3) | ||
− | + | dp[x][y]+=dp[x-2][y+1]; | |
} | } | ||
printf("%llu\n",dp[x1][y1]); | printf("%llu\n",dp[x1][y1]); |
题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因(初次提交分数) |
---|---|---|---|---|---|
骑士游历 | ★☆☆☆☆ | 答案正确 | 100 | 2014/11/28 20:21:12 | 边界问题(50) |
在n*m的棋盘上,马只能从向右走日字格,求(x1,y1)到(x2,y2)的方案数。
dp[x][y]=dp[x][y]+dp[x-1][y-2]+dp[x-1][y+2]+dp[x-2][y-1]+dp[x-2][y+1];
1219.cpp代码已折叠
展开折叠内容
|
---|
#include<cstdio> unsigned long long dp[200][200]={}; int n,m,x0,y0,x1,y1; int main() { scanf("%d%d%d%d%d%d",&n,&m,&x0,&y0,&x1,&y1); dp[x0][y0]=1; for(int x=0;x<=m;++x) for(int y=0;y<=n;++y) { if(x>=2&&y>=3) dp[x][y]=dp[x-1][y-2]; if(x>=2) dp[x][y]+=dp[x-1][y+2]; if(x>=3&&y>=2) dp[x][y]+=dp[x-2][y-1]; if(x>=3) dp[x][y]+=dp[x-2][y+1]; } printf("%llu\n",dp[x1][y1]); } |