首页 > 其他分享 >洛谷P1002 [NOIP2002 普及组] 过河卒 题解

洛谷P1002 [NOIP2002 普及组] 过河卒 题解

时间:2025-01-21 20:04:20浏览次数:3  
标签:洛谷 NOIP2002 int 题解 yb long ym 20 dp

原题链接

题目大意:

棋盘上 A点有一个过河卒,需要走到目标 B 点。

卒行走的规则:向下或向右。

同时在棋盘上 C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

棋盘用坐标表示,AA 点 (0,0)、BB 点 (n,m),同样马的位置坐标是需要给出的。

现在要求你计算出卒从 A点能够到达 B 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。

对于 100% 的数据,1≤n,m≤201≤n,m≤20,0≤0≤ 马的坐标 ≤20≤20。

此题是初级二维DP

1.建立DP数组,dp[i][j]表示卒从A点到点(i,j)的方案数

2.由于卒只能向右或向下,所以当前位置是从dp[i-1][j]和dp[i][j-1]走来的,所以

dp[i][j]=dp[i-1][j]+dp[i][j-1]

3.注意题中下标是从0开始的,不方便,所以我们使下标整体+1

4.有马的存在,我们要跳过马和他的控制点

5. 4中的问题是马的控制点有可能越界,所以我们要把数组内移一位,像这样:

dp[i][j]->dp[i+2][j+2]

6.会爆int,要开long long

7.代码实现:

#include<bits/stdc++.h>
using namespace std;
long long dp[23][23];
int main(){
	int xb,yb,xm,ym;
	cin>>xb>>yb>>xm>>ym;
	xb+=2;
	yb+=2;
	xm+=2;
	ym+=2;
	dp[2][2]=1;
	for(int i=2;i<=xb;i++){
		for(int j=2;j<=yb;j++){
			if((i == xm+1 && j == ym+2)||
			(i==xm+2 && j==ym+1)||
			(i==xm+2 && j==ym-1)||
			(i==xm+1 && j==ym-2)||
			(i==xm-1 && j==ym-2)||
			(i==xm-2 && j==ym-1)||
			(i==xm-2 && j==ym+1)||
			(i==xm-1 && j==ym+2)||
			(i==xm && j==ym))
			continue;
			dp[i][j]+=dp[i-1][j]+dp[i][j-1];
		}
	}
	cout<<dp[xb][yb];
	return 0;
}

标签:洛谷,NOIP2002,int,题解,yb,long,ym,20,dp
From: https://blog.csdn.net/ghhvhgvugft/article/details/145286324

相关文章

  • 2025牛客寒假算法基础集训营1 ptlks的题解
    A.茕茕孑立之影题意:给定序列,找出一个数x,满足x和数组中任意一个元素都互不为倍数关系思路x范围为1e18以内,序列元素范围为1e9以内,选大于1e9的质数即可,特判序列中有1的情况。代码点击查看代码voidsolve(){ intn; cin>>n; intf=1; for(inti=1;i<=n;i++){ cin>>a[......
  • 题解:洛谷 P4879 ycz的妹子
    题目https://www.luogu.com.cn/problem/P4879感觉还比较简单的线段树。首先我们先建立一棵线段树(范围:)。voidbuild(intk,intl,intr){ tr[k]={l,r}; if(l==r){ Tree[k]=a[l],c[k]=(l<=n); return; } intmid=(l+r)>>1ll; build(k<<1ll,l,mid); build((k<<1ll)|1l......
  • 题解:洛谷 P1351 [NOIP2014 提高组] 联合权值
    题目https://www.luogu.com.cn/problem/P1351我们可以发现,若点对  的距离为 ,则它们一定会经过一个中转点,因此我们考虑枚举中转点 ,然后枚举与  有直接边连接的两个点,按照题意统计答案即可。#include<bits/stdc++.h>usingnamespacestd;#pragmaG++optimisze(3,"Ofas......
  • 洛谷题单指南-线段树的进阶用法-P2839 [国家集训队] middle
    原题链接:https://www.luogu.com.cn/problem/P2839题意解读:求左端点在[a,b]之间,右端点在 [c,d]之间的子区间中,最大的中位数。解题思路:1、直男暴力法枚举左、右端点,然后排序计算中位数,这样的复杂度在n*n*logn,显然不可行。2、渣男巧妙法首先,要重新来看待何为中位数。设一段......
  • 【题解】Luogu P4340 [SHOI2016] 随机序列
    简单手摸后发现,答案就是这么一个式子:\[(3^{n-1}-3^{n-2})a_1+(3^{n-2}-3^{n-3})a_1a_2+\dots+(3^1-3^0)a_1a_2\dotsa_{n-1}+a_1a_2\dotsa_n\]啊当然证明也是好证的,对于\(a_1\)这一项,它后面放+或-都会对系数加一,而放*不会影响系数,因此系数就是总数的三分之二。其它前缀......
  • 题解:P3823 [NOI2017] 蚯蚓排队
    题目链接https://www.luogu.com.cn/problem/P3823分析先解决队伍的合并与分离问题。使用链表结构,分别维护每只蚯蚓的前驱和后继即可。然后考虑如何统计答案。可以对每只蚯蚓的“向后\(k\)数字串”使用字符串哈希的方式获得哈希值,再用一个哈希表存储每个哈希值出现的次数。对......
  • 2024 (ICPC) Jiangxi Provincial Contest I 题 Neuvillette Circling题解
    简单思路一个圆套中了几个点,如果不断缩小这个圆,那么最终的结果有两种有两个点卡住了这个圆,且这两点一定是直径有三个或者三个以上的点卡住了这个圆,圆心在这三个点围成的三角形的外接圆圆心。因此我们枚举两点作为直径,或者枚举三个点作为圆的内接三角形,求这个三角形的外接圆......
  • 2024 (ICPC) Jiangxi Provincial Contest L 题 Campus 题解
    简单思路首先对于所有的出口求一遍最短路,由于出口只会打开并关闭一次,所以大门的开启状态是相当有限的(最多大概30种),我们对于每一种状态直接暴力求答案最后输出即可。复杂度大概\(O(knlogn)\)参考代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;type......
  • 洛谷 P3397:地毯 ← “二维前缀和 + 二维差分”模板题
    【题目来源】https://www.luogu.com.cn/problem/P3397【题目描述】在n×n的格子上有m个地毯。给出这些地毯的信息,问每个点被多少个地毯覆盖。【输入格式】第一行,两个正整数n,m。意义如题所述。接下来m行,每行两个坐标(x1,y1)和(x2,y2),代表一块地毯,左上角......
  • Codeforces Round 998 (Div. 3) 部分题解
    写题解的时候这场在评测,就不放代码了。E.GraphComposition题意给两个无向简单图,对图\(1\)添加若干条边或删除若干条边,使得两图的连通性一致,最少需要变更多少条边。题解求出图\(2\)的连通性,考虑图\(1\)的所有边,若违背了图\(2\)联通性的要删除(图\(2\)不联通但图\(......