刷题记录:牛客NC16708[NOIP2002]过河卒
记录 刷题 牛客 过河
2023-09-14 09:12:54 时间
传送门:牛客
题目描述:
如图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一
点有一个对方的马(如上图的C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上
图 C 点上的马可以控制 9 个点(图中的P1,P2 … P8 和 C)。卒不能通过对方马的控制点。
输入:
6 6 3 2
输出:
17
一道经典的dp题,对于这道题我们应该有一个简单的数学储备. 列如下图
这就是一个没有马的路线个数图(假设没有这个知识储备,请自行看图理解,可以手推一下),那么对于这道题我们还有马的限制.所以我们不能只能单单的使用上图,我们还需要进行一些操作.比如因为马的存在,所以在马能吃到的位置我们应该赋值为0(注意,此时的赋值是在dp递推时使用的,而不是递推完之后),因为这个位置是能对后序产生影响的
因此我们的的dp方程也就不难写出了
dp[i][j]=max(dp[i][j],dp[i-1][j]+dp[i][j-1]) 马吃不到的位置
dp[i][j]=0 马吃的到的位置
下面是具体的代码部分:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n,m;
int sx,sy;
int dx[8]={1,-1,-2,-2,-1,1,2,2};
int dy[8]={-2,-2,-1,1,2,2,1,-1};
int vis[100][100];
ll dp[100][100];
int main() {
n=read();m=read();sx=read();sy=read();
n+=2;m+=2;sx+=2;sy+=2;
dp[2][1]=1;
vis[sx][sy]=1;
for(int i=0;i<8;i++) {
vis[sx+dx[i]][sy+dy[i]]=1;
}
for(int i=2;i<=n;i++) {
for(int j=2;j<=m;j++) {
if(vis[i][j]) continue;
dp[i][j]=max(dp[i-1][j]+dp[i][j-1],dp[i][j]);
}
}
printf("%lld\n",dp[n][m]);
return 0;
}
相关文章
- 手机电脑实时同步便签,这个轻量级笔记工具帮你轻松记录知识点
- MySQL-5.6.29源码编译安装记录
- 刷题记录:牛客NC19115选择颜色
- 刷题记录:牛客NC16746神奇盘子
- 刷题记录:牛客NC16597NOIP2011]聪明的质监员
- 刷题记录:牛客NC15434wyh的迷宫
- 刷题记录:牛客NC24911数独挑战
- 刷题记录:牛客NC16498寻找道路
- 刷题记录:牛客NC15553数学考试
- 刷题记录:牛客NC16810拦截导弹
- 刷题记录:牛客NC19996[HAOI2015]树上染色
- 刷题记录:牛客NC51178没有上司的舞会
- 刷题记录:牛客NC16696[NOIP2001]统计单词个数
- 刷题记录:牛客NC22594Rinne Loves Graph
- 刷题记录:牛客NC24370Milk Routing
- 刷题记录:牛客NC53074Forsaken喜欢独一无二的树
- 刷题记录:牛客NC17509挖沟[prim+kruskal算法详解]