题目链接:Codeforces Round #546 (Div. 2) D. Nastya Is Buying Lunch
题意
给出一个长度为n的置换,再给出m组 代表如果ui在vi前面并且相邻时,两者可以交换。问置换中最后一个元素 P[n] 可以最多向前移动几格。
数据范围:
思路
先进行化简,我们的目标等价于找到从n-1开始连续最长的能够被P[n]度过的子串
正向思考超级复杂,
逆向思考就非常简单了
正向思路:维护一个dp[n],复杂度
逆向思路:从后往前扫,如果当前点可以放到那个连续的子串中,就将子串的长度加一,否则找到所有能够到达当前点的u,将他的C数组加一,
C[i]数组所代表的含义是在这i点以后,i点能够穿过多少非P[n]点。
如果当前点能够穿过所有的非连续序列的点,就将这个点++
复杂度 O(n+m),完美
代码
#include <bits/stdc++.h> using namespace std; int N,M,P[1000006],C[1000006],x,y,r; vector<int> g[1000006]; int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin>>N>>M; for(int i=0;i<N;i++) cin>>P[i]; for(int i=0;i<M;i++){ cin>>x>>y; g[y].push_back(x); } for(int i=N-1;i>=0;i--) if(C[P[i]]==N-1-i-r && i!=N-1)r++; else for(int f:g[P[i]])C[f]++; cout<<r; }