首页 > 其他分享 >P1002题解

P1002题解

时间:2024-01-15 22:49:32浏览次数:34  
标签:25 int 题解 P1002 马能 转移 dp

思路

设 \(dp_{i,j}\) 表示第 \(i\) 行 \(j\) 列卒走到这里有多少种方式。

卒是可以向右和下走,所以到这个点只能从左或上来,不难得出转移公式:\(dp_{i,j} = dp_{i-1,j}+dp_{i,j-1}\)。

如果马在这个点上或者说马能到这个点上,那么卒不能到这个点,也就是卒到这个点的方式为 \(0\)。

如何判断马能不能到这个点呢?我们需要一个方向数组,马能走八个方向,依次枚举这八个点是不是当前点即可。

以上就是全部思路,但是还要注意一下几点:

  • \(dp_{0,0}\) 赋值为 \(1\),初始化。
  • 在转移过程中会数组越界,所以需要判断。
  • 转移时如果当前点是 \((0,0)\) 则不进行转移,因为这是初始点,已经有值了。

AC CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[25][25];
int dx[8]={-1,-2,-2,-1,1,2,2,1},dy[8]={-2,-1,1,2,2,1,-1,-2};
signed main(){
	int n,m,x,y;
	cin>>n>>m>>x>>y;
	dp[0][0]=1;//初始值
	bool ok=1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(i==0&&j==0)continue;//不能是初始点
			ok=1;
			if(i==x&&j==y)ok=0;//这个点是不是马的位置
			for(int k=0;k<8;k++){//这个点有没有被马控制
				if(i==x+dx[k]&&j==y+dy[k]){ok=0;break;}
			}
			if(ok){//转移
				if(i-1<0){//判断越界
					dp[i][j]=dp[i][j-1];
				}
				else if(j-1<0){
					dp[i][j]=dp[i-1][j];
				}
				else{
					dp[i][j]=dp[i-1][j]+dp[i][j-1];	
				}
				
			}
		} 
	}
	cout<<dp[n][m]<<endl;
	return 0;
}

标签:25,int,题解,P1002,马能,转移,dp
From: https://www.cnblogs.com/xdh2012/p/17966555

相关文章

  • P1003题解
    简单模拟题。思路枚举每一个地毯,因为后面的会覆盖前面的,所以从正序枚举。如果要求的点的坐标在当前地毯上,则将答案赋值为当前地毯编号。最后输出答案。那如果这个点没有地毯呢?答案初始设为\(-1\),这样没有地毯覆盖的话,答案不会改变,这样输出答案就会是\(-1\)。注意:记得赋初......
  • P10058题解
    怎么前三题都是思维题啊。思路总共有三个操作,先不看翻转操作。如果你右移\(x\)位之后,左移\(x\)位,那么就相当于没有操作。这个应该是很好理解的。我们根据上面的结论,能得出以下代码。if(op==">"){cin>>x;f+=x;}elseif(op=="<"){......
  • CF1409D题解
    思路因为数据较大,使用字符串读入。考虑使用贪心。先统计出当前数码之和。然后从低位往高位枚举,看一下把当前位改了之后是否小于等于\(s\)。如果小于的话,则统计出把当前位往后所有位都改为0,\(k\)为多少,求出的\(k\)就是最优解。说明一下为什么要从低位往高位枚举,这样如果成......
  • AT_arc060_c题解
    纪念模拟考考挂。思路首先二分查找出当前点往后走最远能去哪个点,当前点为\(i\),记最远能去的那个点为\(nt_i\)。考虑建一棵树,将\(nt_i\)设为\(i\)点的父节点。暴力的话直接从当前点往上找,找到目标节点看几次就好了。但显然是过不了的。考虑使用倍增优化。设\(g_{i,j}......
  • 1.15模拟赛 T2题解
    简要题意多重背包但是乘法思路暴力就直接跑背包考虑乘法能否变为加法,可以找到模数的原根,将每个数映射一下,这样乘法就变成了加法,可以直接\(\text{bitset}\)优化,但是暴力这样做还是过不了于是我们考虑二进制分组优化背包,这样复杂度貌似就对了?code#pragmaGCCoptimize("Ofast......
  • border设置渐变boder-radius不生效问题解决方案
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"/><metahttp-equiv="X-UA-Compatible"content="IE=edge"/><metaname="viewport"c......
  • 【题解】gym103743 (2022 JSCPC)
    A.PENTAKILL!考虑直接模拟,规则就是一个人将其他人全部都击杀,并且中间没有重复击杀。code:#include<bits/stdc++.h>usingnamespacestd;map<string,vector<string>>st;intn;stringa,b;intmain(){cin>>n;for(inti=1;i<=n;++i){ci......
  • 题解「JOI 2014 Final」IOI 馒头
    传送门。题意有\(n\)个物品,\(m\)个背包。第\(i\)个物品的价值是\(P_i\),第\(j\)个背包可以装\(C_i\)个物品,但会消耗\(E_i\)的价值。背包不能重复买,问最多可以获得多少价值。分析首先一个简单的贪心,我们在购买背包后塞入物品,一定时从大往小塞,也就是说,我们可以先对......
  • abc336 E - Digit Sum Divisible 题解 数位DP
    题目链接:https://atcoder.jp/contests/abc336/tasks/abc336_e题目大意:我们定义一个整数\(n\)的数位和为\(n\)的十进制表示中的各位上的数字之和。比如:整数\(2024\)的数位和为\(2+0+2+4=8\)。一个正整数\(n\)被称作一个好数如果\(n\)能被它的数位和整除......
  • CF1818B ndivisible 题解
    题意简述构造一个长度为\(n\)的排列\(A\),使得对于任意的\(l,r\)(\(1\lel<r\len\))都满足\(A_l+A_{l+1}+⋯+A_r\)不可以被\(r-l+1\)整除。输出其中一种合法排列即可。解题思路构造题。考虑对\(n\)进行分类讨论:当\(n=1\)时,由样例即可得合法排列为\(1\)......