VJ地址

題意：選擇一段or兩段連續(xù)的區(qū)間，合成一段序列，使得選擇的序列中沒有相同的數(shù)字，求序列最長的長度

思路：由于是區(qū)間內(nèi)不能有相同的數(shù)字，所以考慮用尺取，可以2*n的時間枚舉第一段的長度，然后剩下兩邊的區(qū)間，同樣用尺取找到能選擇的最大值，然后相加，做法挺暴力，不過數(shù)據(jù)小啊。

#include<bits/stdc++.h> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define rep(i,n) for(int i=0;(i)<(n);i++) #define rep1(i,n) for(int i=1;(i)<=(n);i++) #define se secondusing namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int > pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=1e9+7; const ll N =2e6+10; const double eps = 1e-4; const double pi=acos(-1); ll gcd(int a,int b){return !b?a:gcd(b,a%b);} int vis[N]; int cc; int n; int a[N]; int work(int L,int R){if(L>R) return 0;int l=L,r=L;int ans=0;while(r<=R||l<=R){while(!vis[a[r]]&&r<=R){vis[a[r++]]++;ans=max(ans,r-l);}if(l>=r&&vis[a[r]]) vis[a[r++]]++;vis[a[l]]--;l++;ans=max(ans,r-l);}return ans; } int main() {iosint t;cin>>t;while(t--){FILL(vis,0);cin>>n;rep1(i,n){cin>>a[i];}int L=1,R=1;int ans=0;while(R<=n){while(!vis[a[R]]&&R<=n){vis[a[R++]]++;ans=max(ans,R-L+max(work(1,L-1),work(R,n)));}vis[a[L]]--;L++;ans=max(ans,R-L+max(work(1,L-1),work(R,n)));}printf("Case #%d: %d\n",++cc,ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的C - Mr. Panda and Strips Gym - 101194C(思维//尺取//2016 icpc china final)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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