codeforces 1364B（数学）

dejavu1zz

发布于 2020-10-23 15:20:59

27900

代码可运行

文章被收录于专栏：奇妙的算法世界奇妙的算法世界

运行总次数：0

代码可运行

题意描述

Given a permutation p of length n, find its subsequence s1, s2, …, sk of length at least 2 such that:

|s1−s2|+|s2−s3|+…+|sk−1−sk| is as big as possible over all subsequences of p with length at least 2. Among all such subsequences, choose the one whose length, k, is as small as possible. If multiple subsequences satisfy these conditions, you are allowed to find any of them.

A sequence a is a subsequence of an array b if a can be obtained from b by deleting some (possibly, zero or all) elements.

A permutation of length n is an array of length n in which every element from 1 to n occurs exactly once.

寻找子序列，要求相邻两个数的绝对值和最大，并且序列长度最小

思路

我们发现有两种情况：

通过观察可以发现，首尾需要添加。然后寻找峰值即可。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=1e5+10;
const int M=1e6+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
int a[N];
void solve(){
    int n;cin>>n;
    rep(i,1,n+1) cin>>a[i];
    vector<int> ans;
    ans.PB(a[1]);
    rep(i,2,n){
        if(a[i-1]<a[i] && a[i]>a[i+1]){
            ans.PB(a[i]);
        }
        if(a[i-1]>a[i] && a[i+1]>a[i]){
            ans.PB(a[i]);
        }
    }
    ans.PB(a[n]);
    cout<<ans.size()<<endl;
    rep(i,0,ans.size()) cout<<ans[i]<<' ';
    cout<<endl;
}
int main(){
    IOS;
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/08/01 ，如有侵权请联系 cloudcommunity@tencent.com 删除

element