P6704 [COCI2010-2011#7] GITARA 详细题解

题目传送门

题目背景

Darko 有一个想象的外星朋友，他有十亿根手指。外星人快速拿起吉他，在网上找到一段简单的旋律并开始弹奏。

这个吉他像寻常一样有六根弦，令其用 1 到 6 表示。每根弦被分成 P 段，令其用 1 到 P表示。

旋律是一串的音调，每一个音调都是由按下特定的一根弦上的一段而产生的（如按第 4弦第 8段）。如果在一根弦上同时按在几段上，产生的音调是段数最大的那一段所能产生的音调。

例：对于第 3根弦，第 5段已经被按，若你要弹出第 7段对应音调，只需把按住第 7段，而不需放开第 5 段，因为只有最后的一段才会影响该弦产生的音调(在这个例子中是第 7 段)。类似，如果现在你要弹出第 2段对应音调，你必须把第 5 段和第 7 段都释放。

请你编写一个程序，计算外星人在弹出给定的旋律情况下，手指运动的最小次数。

题目描述

你有一个 6×P 的矩阵 A，初始状态皆为 0。

对于所有要求 (i,j)

你需要满足要求：

1. 此时 $A_{i,j}$状态为 1。
2. 对于 $A_{i,j+k}(k>0)$状态为 0。

你在满足要求的情况下需要求状态转换最小次数。

输入格式

第一行包含两个正整数 n ，P。它们分别指旋律中音调的数量及每根弦的段数。

下面的 n 行每行两个正整数 i，j，分别表示能弹出对应音调的位置——弦号和段号，其为外星人弹奏的顺序。

输出格式

一个非负整数表示外星人手指运动次数最小值。

解题思路：

题目要求高段可以直接按下，而低段必须松开该弦上按着高段的手指才能按下。所以我们把每根弦看做一个栈，把整个琴看做栈数组,并且特别注意一下这里的栈操作其实就是单调栈的操作。
$$\{\begin{array}{l}1.栈非空\{\begin{array}{l}1.弹出栈中更高段并统计数加一，直到栈空或者没有更高段。\\ 2.栈空？\{\begin{array}{l}1.空，直接压栈并统计数加一。\\ 2.非空，栈顶是否为更低段？\{\begin{array}{l}1.为更低段，压栈并统计数加一\\ 2.为同一段，不做任何处理\end{array}\end{array}\end{array}\\ 2.栈空：直接压栈并统计数加一。\end{array}$$
这里再放一个单个琴弦的动图来做理解：

附上代码：

#include<bits/stdc++.h>//又是STL催肥机
using namespace std;#define ll long long
#define INF 0x3f3f3f3fstack<int> st[7];//创建栈数组
int cnt;//统计手指活动次数int main(){ios::sync_with_stdio(0);cin.tie(0);int n,p;cin >> n >> p;//输入音调数与弦段数while(n--){int i,j;cin >> i >> j;//输入第几根琴弦的第几段if(st[i].size()){//如果栈非空while(st[i].size() && st[i].top() > j){//在栈非空的情况下，弹出所有更高段，并统计数加一st[i].pop();cnt++;}if(st[i].empty() || j > st[i].top()){//如果栈空，或者栈顶的段低于要演奏的段，则压栈，统计数加一st[i].push(j);cnt++;}}else{//如果栈空，则直接按下，压栈，统计数加一st[i].push(j);cnt++;}}cout << cnt;//输出结果return 0;//保持好习惯
}