題目鏈接

題意：讓求|s1-s2|+|s2-s3|+…|sk-1 - sk|最大時的最短序列。

思路：去掉絕對值之后我們發現如果每三個數是有序的那么我們可以消去中間的數不影響答案，看能消多少。

#include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<iostream> #include<bits/stdc++.h> using namespace std; typedef long long ll; #define space putchar(' ') #define enter putchar('\n') typedef pair<int,int> PII; const int mod=1e4+7; const int N=2e5+10; const int inf=0x7f7f7f7f;ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b); }ll lcm(ll a,ll b) {return a*(b/gcd(a,b)); }template <class T> void read(T &x) {char c;bool op = 0;while(c = getchar(), c < '0' || c > '9')if(c == '-')op = 1;x = c - '0';while(c = getchar(), c >= '0' && c <= '9')x = x * 10 + c - '0';if(op)x = -x; } template <class T> void write(T x) {if(x < 0)x = -x, putchar('-');if(x >= 10)write(x / 10);putchar('0' + x % 10); } int vis[N]; int a[N];int main() {int t;cin>>t;while(t--){memset(vis,0,sizeof vis);int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}int ans=n;for(int i=2;i<=n-1;i++){if((a[i]<=a[i-1]&&a[i]>=a[i+1])||(a[i]>=a[i-1]&&a[i]<=a[i+1])){vis[i]++;ans--;}}cout<<ans<<endl;for(int i=1;i<=n;i++){if(!vis[i])cout<<a[i]<<endl;}cout<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的Codeforces round #649 B. Most socially-distanced subsequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。