[TIOJ 1691] Problem A 圍籬架設問題

作法：

兩個子序列一定有一個位置不一樣，那麼大概可以想到兩個子序列的前後一定是一整排一樣的東西，只有中間一點點不一樣。其實只要找到 i 和 j 使得 a[ i ] = a[ j ] 且 i != j ，那麼考慮第一個子序列取 a[ 1 ] ~ a[ i ] , a[ j + 1 ] ~ a[ n ] ，第二個子序列取 a[ 1 ] ~ a[ i - 1 ] , a[ j ] ~ a[ n ] ，就可以得到其中一組解，並且可以知道最佳解一定長成這樣，所以只要找到 j - i 最小且 a[ j ] = a[ i ] 的 j - i 的值就好了。

code :

#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
 
map<int,vector<int> > mp ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        int x  ; scanf("%d",&x) ;
        mp[x].push_back(i) ;
    }
    int mi=n ;
    for(auto i : mp) for(int j=0;j<(int)i.S.size()-1;j++)
        mi=min(mi,i.S[j+1]-i.S[j]) ;
    printf("%d\n",n-mi) ;
}