刷题记录:牛客NC16708[NOIP2002]过河卒

传送门:牛客

题目描述:

如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一
点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上
图 C 点上的马可以控制 9 个点（图中的P1，P2 … P8 和 C）。卒不能通过对方马的控制点。
输入:
6 6 3 2
输出:
17
1
2
3
4
5
6
7

一道经典的dp题,对于这道题我们应该有一个简单的数学储备. 列如下图

这就是一个没有马的路线个数图(假设没有这个知识储备,请自行看图理解,可以手推一下),那么对于这道题我们还有马的限制.所以我们不能只能单单的使用上图,我们还需要进行一些操作.比如因为马的存在,所以在马能吃到的位置我们应该赋值为0(注意,此时的赋值是在dp递推时使用的,而不是递推完之后),因为这个位置是能对后序产生影响的

因此我们的的dp方程也就不难写出了

dp[i][j]=max(dp[i][j],dp[i-1][j]+dp[i][j-1])    马吃不到的位置

dp[i][j]=0    马吃的到的位置

下面是具体的代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49