题解题解【NOIP2016普及组复赛模拟赛】侦察兵
hymcr05
题目描述
mxy 沉迷于一个辣鸡游戏不可自拔。
游戏地图是一个 n*n 的矩形，在每个单位格子上有一个数字，代表当前位置的生命体个数，作为一个侦察兵，mxy 的任务是计算出她所在位置的左上角和右下角的总人数（不包括她所在的行列）。
注意作为一个侦察兵，mxy 是不包括在地图上的生命体个数中的。
输入
从文件 scout.in 中读入数据。
第一行 2 个整数 n 和 t。（1≤n≤1000，1≤t≤1000）
接下来 n 行，每行 n 个整数表示每个单位格子上的生命体个数 a。（1≤a≤100）
再下来 t 行，每行两个整数 xi，yi，表示不同时刻 mxy 在地图上的位置。
输出
输出到文件 scout.out 中。
T 行，每行一个整数，表示当前时刻 mxy 所在位置的左上角和右下角的总人数。
样例输入
1
2
3
4
5
6
| 4 1
0 1 2 0
3 2 0 0
1 2 3 2
0 0 0 10
3 3
|
样例输出
正片开始！！！
首先，先来画个图推理一下
没错，只是一道DP题（其实就是2维前缀和)
OK，直接开始撸代码：
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
| #include <bits/stdc++.h>
using namespace std;
int n, t;
int a[1002][1002],fx[1002][1002],fy[1002][1002];
int ans1,ans2;
int sx, sy;
int main() {
freopen("scout.in", "r", stdin);
freopen("scout.out", "w", stdout);
cin >> n >> t;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
for(int i=2; i<=n; i++) {
for(int j=2; j<=n; j++) {
fx[i][j]=fx[i][j-1]+fx[i-1][j]-fx[i-1][j-1]+a[i-1][j-1];
}
}
for(int i=n-1; i>=1; i--) {
for(int j=n-1; j>=1; j--) {
fy[i][j]=fy[i][j+1]+fy[i+1][j]-fy[i+1][j+1]+a[i+1][j+1];
}
}
for(int i=1; i<=t; ++i) {
cin >> sx >> sy;
cout << fx[sx][sy]+fy[sx][sy]<<endl;
}
return 0;
}
|
再见！！！
