題解 - $\mathrm{C}\mathrm{F}1364\mathrm{B}$

題目意思

• 題目傳送門

$\mathrm{S}\mathrm{o}\mathrm{l}$

• 首先我們考慮一個性質(zhì)，如何才能使得貢獻(xiàn)盡量大。畫幾個圖看看

對于第一種一條直線類型的它的實際貢獻(xiàn)就是$|c?a|$，而對于第二種它的貢獻(xiàn)就為$|a?d|+|d?b|+...|c?e|$。發(fā)現(xiàn)能產(chǎn)生貢獻(xiàn)的情況就是那種峰，谷的情況，于是我們記錄這些拐點即可。時間復(fù)雜度$O(n)$

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <bits/stdc++.h> #define For(i,a,b) for ( int i=(a);i<=(b);i++ ) #define Dow(i,b,a) for ( int i=(b);i>=(a);i-- ) #define GO(i,x) for ( int i=head[x];i;i=e[i].nex ) #define mem(x,s) memset(x,s,sizeof(x)) #define cpy(x,s) memcpy(x,s,sizeof(x)) #define YES return puts("YES"),0 #define NO return puts("NO"),0 #define GG return puts("-1"),0 #define pb push_back using namespace std;inline int read() {int sum=0,ff=1; char ch=getchar();while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}while(isdigit(ch))sum=sum*10+(ch^48),ch=getchar();return sum*ff; }const int mod=1e9+7; const int mo=998244353; const int N=1e5+5;int n,m,Q,a[N],b[N],ans;int main() {Q=read();For(q,1,Q){n=read();For(i,1,n) a[i]=read();b[m=1]=1;For(i,2,n-1) if((a[i]>a[i-1]&&a[i]>a[i+1])||(a[i]<a[i-1]&&a[i]<a[i+1])) b[++m]=i;b[++m]=n;printf("%d\n",m);For(i,1,m) printf("%d ",a[b[i]]);puts("");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的题解 CF1364B Most socially-distanced subsequence的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。