洛谷P1004方格取数（两个题解）P1359租用游艇 P2285打鼹鼠 P1725琪露诺 P1886滑动窗口/单调序列
P1004 [NOIP 2000 提高组] 方格取数
题目背景
NOIP 2000 提高组 T4
题目描述
设有 N × N N \times N N×N 的方格图 ( N ≤ 9 ) (N \le 9) (N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0 0 0。如下图所示（见样例）:
某人从图的左上角的
A
A
A 点出发，可以向下行走，也可以向右走，直到到达右下角的
B
B
B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字
0
0
0）。
此人从
A
A
A 点到
B
B
B 点共走两次，试找出
2
2
2 条这样的路径，使得取得的数之和为最大。
输入格式
输入的第一行为一个整数 N N N（表示 N × N N \times N N×N 的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 0 0 0 表示输入结束。
输出格式
只需输出一个整数，表示 2 2 2 条路径上取得的最大的和。
输入输出样例 #1
输入 #1
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输出 #1
67
说明/提示
数据范围： 1 ≤ N ≤ 9 1\le N\le 9 1≤N≤9。
#include<bits/stdc++.h>
using namespace std;
int x,y,z,n,a[12][12],f[12][12][12][12];
int main(){
cin >> n >> x >> y >> z;
while(x!=0||y!=0||z!=0) {
a[x][y] = z;
cin >> x >> y >> z;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 1; k <= n; k++)
for(int l = 1; l <= n; l++){
f[i][j][k][l] = max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]))+a[i][j]+a[k][l];
if(i==k&&j==l)f[i][j][k][l]-=a[i][l];
}
cout << f[n][n][n][n];
return 0;
}
附上次的题解
某人从图的左上角的
A
A
A 点出发，可以向下行走，也可以向右走，直到到达右下角的
B
B
B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字
0
0
0）。
此人从
A
A
A 点到
B
B
B 点共走两次，试找出
2
2
2 条这样的路径，使得取得的数之和为最大。
题解：深搜，因为要两条路都而且是两条路同时进行，每次经过一个点，相加在改值为零，自己写的时候时间复杂度太高而且遍历没有考虑重复，看题解区有所剪枝,注意在（n,n）点回去的时候要减去其值，可以当成一条路，从A到B再回到A
第一条路f=0，第二条路f=1
#include<bits/stdc++.h>
using namespace std;
const int dx[]={0, 1, 0, -1},dy[]={1, 0, -1, 0};
int map[10][10], n;
int max1=0，ans=0;
inline void dfs(int x, int y, int z, int f)
{
if (x<1||y<1||x>n||y>n) return;
if (x==n&&y==n)
{
f=1;
z-=map[n][n];
if (z>max1)
max1=max(max1, z);
else
return;
}
if (x==1&&y==1&&f==1) //
ans=max(ans, z);
if (!f)
{
for (int i=0; i<2; i++)
{
int lx=x+dx[i],ly=y+dy[i],t=map[lx][ly];
map[lx][ly]=0;
dfs(lx, ly, z+t, f);
map[lx][ly]=t;
}
}
else //第二条路
{
for (int i=2; i<4; i++)
{
int rx=x+dx[i], ry=y+dy[i], t=map[rx][ry];
map[rx][ry]=0;
dfs(rx, ry, z+t, f);
map[rx][ry]=t;
}
}
}
int main()
{
cin>>n;
while(1)
{
int x, y, z;
cin>>x>>y>>z;
if (x==0 && y==0 && z==0)
break;
map[x][y]=z;
}
dfs(1, 1, 0, 0);
cout<<ans<<endl;
return 0;
}
P1359 租用游艇
题目描述
长江游艇俱乐部在长江上设置了 n n n 个游艇出租站 1 , 2 , ⋯ , n 1,2,\cdots,n 1,2,⋯,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i i i 到游艇出租站 j j j 之间的租金为 r ( i , j ) r(i,j) r(i,j)（ 1 ≤ i < j ≤ n 1\le i\lt j\le n 1≤i<j≤n）。试设计一个算法，计算出从游艇出租站 1 1 1 到游艇出租站 n n n 所需的最少租金。
输入格式
第一行中有一个正整数 n n n，表示有 n n n 个游艇出租站。接下来的 n − 1 n-1 n−1 行是一个半矩阵 r ( i , j ) r(i,j) r(i,j)（ 1 ≤ i < j ≤ n 1\le i<j\le n 1≤i<j≤n）。
输出格式
输出计算出的从游艇出租站 1 1 1 到游艇出租站 n n n 所需的最少租金。
输入输出样例 #1
输入 #1
3
5 15
7
输出 #1
12
说明/提示
n ≤ 200 n\le 200 n≤200，保证计算过程中任何时刻数值都不超过 1 0 6 10^6 106。
Floyd算法，图只有上三角，事实上有没有向都是一样的，因为循环中 j = i + 1并不会考虑下三角
#include <bits/stdc++.h>
using namespace std;
#define N 1010
int n, a[N][N], dp[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++) {
if (i == 1)
dp[i] = 0;
else
dp[i] = a[1][i];
}
for (int k = 2; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = i+1; j <= n; j++) {
if (i != j && a[i][j] != 0) {
dp[j] = min(dp[j], dp[i] + a[i][j]);
}
}
}
}
cout << dp[n] ;
return 0;
}
P2285 [HNOI2004] 打鼹鼠
题目描述
鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿牛编写了一个打鼹鼠的游戏：在一个 n × n n \times n n×n 的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果 i i i 时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为 ( i , j ) (i, j) (i,j) 的网格移向 ( i − 1 , j ) , ( i + 1 , j ) , ( i , j − 1 ) , ( i , j + 1 ) (i-1, j), (i+1, j), (i, j-1), (i, j+1) (i−1,j),(i+1,j),(i,j−1),(i,j+1) 四个网格，机器人不能走出整个 n × n n \times n n×n 的网格。游戏开始时，你可以自由选定机器人的初始位置。
现在知道在一段时间内，鼹鼠出现的时间和地点，请编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。
输入格式
第一行为 n , m n, m n,m（ n ≤ 1000 n \le 1000 n≤1000， m ≤ 10 4 m \le {10}^4 m≤104），其中 m m m 表示在这一段时间内出现的鼹鼠的个数，接下来的 m m m 行中每行有三个数据 t i m e , x , y \mathit{time}, x, y time,x,y 表示在游戏开始后 t i m e \mathit{time} time 个时刻，在第 x x x 行第 y y y 个网格里出现了一只鼹鼠。 t i m e \mathit{time} time 按递增的顺序给出。注意同一时刻可能出现多只鼹鼠，但同一时刻同一地点只可能出现一只鼹鼠。
输出格式
仅包含一个正整数，表示被打死鼹鼠的最大数目。
输入输出样例 #1
输入 #1
2 2
1 1 1
2 2 2
输出 #1
1
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
struct node
{
int t,x,y;
}mou[10005];
int n,m,ans=-1e9,dp[10005];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&mou[i].t,&mou[i].x,&mou[i].y);
}
for(int i=1;i<=m;i++)
{
dp[i]=1; //以第i只鼹鼠结尾的打鼹鼠序列
for(int j=1;j<i;j++) //枚举前面的鼹鼠
{
int ddx=abs(mou[i].x-mou[j].x);
int ddy=abs(mou[i].y-mou[j].y);
int len=ddx+ddy;//曼哈顿距离
int time=mou[i].t-mou[j].t;
if(time>=len)
{
dp[i]=max(dp[i],dp[j]+1);
}
}
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
return 0;
}
P1725 琪露诺
题目描述
在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。
某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。
小河可以看作一列格子依次编号为 0 0 0 到 N N N，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子 i i i 时，她只移动到区间 [ i + L , i + R ] [i+L,i+R] [i+L,i+R] 中的任意一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。
每一个格子都有一个冰冻指数 A i A_i Ai，编号为 0 0 0 的格子冰冻指数为 0 0 0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数 A i A_i Ai。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。
但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。
开始时，琪露诺在编号 0 0 0 的格子上，只要她下一步的位置编号大于 N N N 就算到达对岸。
输入格式
第一行三个正整数 N , L , R N, L, R N,L,R。
第二行共 N + 1 N+1 N+1 个整数，第 i i i 个数表示编号为 i − 1 i-1 i−1 的格子的冰冻指数 A i − 1 A_{i-1} Ai−1。
输出格式
一个整数，表示最大冰冻指数。
输入输出样例 #1
输入 #1
5 2 3
0 12 3 11 7 -2
输出 #1
11
说明/提示
对于 60 % 60\% 60% 的数据， N ≤ 1 0 4 N \le 10^4 N≤104。
对于 100 % 100\% 100% 的数据， N ≤ 2 × 1 0 5 N \le 2\times 10^5 N≤2×105，数据保证最终答案不超过 2 31 − 1 2^{31}-1 231−1。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,l,r,a[400005];
deque<int>q;
cin >> n >> l >> r;
for(int i = 0; i <= n; i++)cin >> a[i];
q.push_back(n+1);//把末尾之后的0放进去
for(int i = n - l ;i >= 0; i--){//必须从后面开始，然后迭代回去，对于每个i都只需要考虑i+l到i+r的窗口，我们从n-l开始
if(q.front() > i+r)q.pop_front();//如果队首大于窗口，那么弹出
if(!q.empty()){
while(a[i+l]>a[q.back()]){//新进来的元素大于原来窗口的最大值的话
q.pop_back();//就把最大值弹出
if(q.empty())break;//一直弹出到空就退出
}
}
q.push_back(i+l);//那么如果队列空就直接加
a[i] += a[q.front()];//因此a[i]只需要加上其对应窗口的最大值即a[q.front()]就好了
}
cout << a[0] ;
return 0;
}
这道题有涉及到单调队列，再来看看洛谷P1886模板单调序列
P1886 滑动窗口 /【模板】单调队列
题目描述
有一个长为 n n n 的序列 a a a，以及一个大小为 k k k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如，对于序列 [ 1 , 3 , − 1 , − 3 , 5 , 3 , 6 , 7 ] [1,3,-1,-3,5,3,6,7] [1,3,−1,−3,5,3,6,7] 以及 k = 3 k = 3 k=3，有如下过程：
窗口位置 最小值 最大值 [1 3 -1] -3 5 3 6 7 − 1 3 1 [3 -1 -3] 5 3 6 7 − 3 3 1 3 [-1 -3 5] 3 6 7 − 3 5 1 3 -1 [-3 5 3] 6 7 − 3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7 \def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array} 窗口位置[1 3 -1] -3 5 3 6 7 1 [3 -1 -3] 5 3 6 7 1 3 [-1 -3 5] 3 6 7 1 3 -1 [-3 5 3] 6 7 1 3 -1 -3 [5 3 6] 7 1 3 -1 -3 5 [3 6 7]最小值−1−3−3−333最大值335567
输入格式
输入一共有两行，第一行有两个正整数
n
,
k
n,k
n,k。
第二行
n
n
n 个整数，表示序列
a
a
a
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入输出样例 #1
输入 #1
8 3
1 3 -1 -3 5 3 6 7
输出 #1
-1 -3 -3 -3 3 3
3 3 5 5 6 7
说明/提示
【数据范围】
对于
50
%
50\%
50% 的数据，
1
≤
n
≤
1
0
5
1 \le n \le 10^5
1≤n≤105；
对于
100
%
100\%
100% 的数据，
1
≤
k
≤
n
≤
1
0
6
1\le k \le n \le 10^6
1≤k≤n≤106，
a
i
∈
[
−
2
31
,
2
31
)
a_i \in [-2^{31},2^{31})
ai∈[−231,231)。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7+10;
int a[N] , q[N];
int main(){
int n , k ;
cin >> n >> k;
for(int i = 1; i <= n ; i++)cin >> a[i];
//维护窗口内的升序子序列 (维护最小值)
int h = 1, t = 0;//在窗口中h在左，t在右
for(int i = 1; i<=n;i++){
while(h <= t && a[q[t]] >= a[i])t--;//新元素更小那么队尾出队
q[++t] = i; //队尾入队（存储队尾的下标，方便判断队头出队）
if(q[h] < i - k + 1) h++;//队头出队（队头（队头的下标）的元素滑出窗口）
if(i >= k)cout << a[q[h]] << " ";
}
cout << endl;
//维护窗口内的降序子序列（维护最大值）
h = 1,t = 0;
for(int i = 1; i<=n; i++){
while(h <= t && a[q[t]] <= a[i])t--;
q[++t] = i;
if(q[h] < i - k + 1) h++;
if(i >= k)cout << a[q[h]] << " ";
}
}
