洛谷P1004方格取数（两个题解）P1359租用游艇 P2285打鼹鼠 P1725琪露诺 P1886滑动窗口/单调序列

NOIP 2000 提高组 T4。

骑驴看星星a

763人浏览 · 2025-03-02 15:37:02

骑驴看星星a · 2025-03-02 15:37:02 发布

P1004 [NOIP 2000 提高组] 方格取数

题目背景

NOIP 2000 提高组 T4

题目描述

设有 $\times N$ 的方格图 $\le 9)$ ，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 $0$ 。如下图所示（见样例）:

某人从图的左上角的 $A$ 点出发，可以向下行走，也可以向右走，直到到达右下角的 $B$ 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 $0$ ）。
此人从 $A$ 点到 $B$ 点共走两次，试找出 $2$ 条这样的路径，使得取得的数之和为最大。

输入格式

输入的第一行为一个整数 $N$ （表示 $\times N$ 的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 $0$ 表示输入结束。

输出格式

只需输出一个整数，表示 $2$ 条路径上取得的最大的和。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

数据范围： $1≤N≤91\le N\le 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$ 点出发，可以向下行走，也可以向右走，直到到达右下角的 $B$ 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 $0$ ）。
此人从 $A$ 点到 $B$ 点共走两次，试找出 $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$ 个游艇出租站 $,n1,2,\cdots,n$ 。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 $i$ 到游艇出租站 $j$ 之间的租金为 $r (i, j)$ （ $1≤i<j≤n1\le i\lt j\le n$ ）。试设计一个算法，计算出从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。

输入格式

第一行中有一个正整数 $n$ ，表示有 $n$ 个游艇出租站。接下来的 $n - 1$ 行是一个半矩阵 $r (i, j)$ （ $1≤i<j≤n1\le i<j\le n$ ）。

输出格式

输出计算出的从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。

输入输出样例 #1

输入 #1

3
5 15
7

输出 #1

说明/提示

$n≤200n\le 200$ ，保证计算过程中任何时刻数值都不超过 $10^6$ 。

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] 打鼹鼠

题目描述

鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿牛编写了一个打鼹鼠的游戏：在一个 $\times n$ 的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果 $i$ 时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为 $(i, j)$ 的网格移向 $(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)$ 四个网格，机器人不能走出整个 $\times n$ 的网格。游戏开始时，你可以自由选定机器人的初始位置。

现在知道在一段时间内，鼹鼠出现的时间和地点，请编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。

输入格式

第一行为 $n, m$ （ $\le 1000$ ， $\le {10}^4$ ），其中 $m$ 表示在这一段时间内出现的鼹鼠的个数，接下来的 $m$ 行中每行有三个数据 $time,x,y\mathit{time}, x, y$ 表示在游戏开始后 $time\mathit{time}$ 个时刻，在第 $x$ 行第 $y$ 个网格里出现了一只鼹鼠。 $time\mathit{time}$ 按递增的顺序给出。注意同一时刻可能出现多只鼹鼠，但同一时刻同一地点只可能出现一只鼹鼠。

输出格式

仅包含一个正整数，表示被打死鼹鼠的最大数目。

输入输出样例 #1

输入 #1

2 2	         
1 1 1		
2 2 2

输出 #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$ 到 $N$ ，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子 $i$ 时，她只移动到区间 $[i + L, i + R]$ 中的任意一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。

每一个格子都有一个冰冻指数 $A_i$ ，编号为 $0$ 的格子冰冻指数为 $0$ 。当琪露诺停留在那一格时就可以得到那一格的冰冻指数 $A_i$ 。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。

但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。

开始时，琪露诺在编号 $0$ 的格子上，只要她下一步的位置编号大于 $N$ 就算到达对岸。

输入格式

第一行三个正整数 $N, L, R$ 。

第二行共 $N + 1$ 个整数，第 $i$ 个数表示编号为 $i - 1$ 的格子的冰冻指数 $A_{i-1}$ 。

输出格式

一个整数，表示最大冰冻指数。

输入输出样例 #1

输入 #1

5 2 3
0 12 3 11 7 -2

输出 #1

说明/提示

对于 $60%60\%$ 的数据， $\le 10^4$ 。

对于 $100%100\%$ 的数据， $\le 2\times 10^5$ ，数据保证最终答案不超过 $2^{31}-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$ 的序列 $a$ ，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如，对于序列 $[1, 3, - 1, - 3, 5, 3, 6, 7]$ 以及 $k = 3$ ，有如下过程：

$7]37\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}$

输入格式

输入一共有两行，第一行有两个正整数 $n, k$ 。
第二行 $n$ 个整数，表示序列 $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\%$ 的数据， $\le n \le 10^5$ ；
对于 $100%100\%$ 的数据， $1≤k≤n≤1061\le k \le n \le 10^6$ ， $ai∈[−231,231)a_i \in [-2^{31},2^{31})$ 。

#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]] << " ";
	}

}