Submission #73430240

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// #define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

struct fast_io{fast_io(){cin.tie(nullptr)->sync_with_stdio(false);}}_;
template<class T> bool chmax(T &a,T b){return (a<b)?a=b,1:0;}
template<class T> bool chmin(T &a,T b){return (a>b)?a=b,1:0;}

template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>;

vector<int> vidx[20][20];

signed main(){
	int N;cin>>N;
	vector<int> A(N);for(auto&&e:A)cin>>e,e--;

	int M=*max_element(all(A))+1;

	auto add=[&](int s,int x)->int {
		assert(!(s>>x&1));
		rrep(i,x){
			if(s>>i&1){
				s^=(1<<i);
				s^=(1<<x);
				return s;
			}
		}
		s^=(1<<x);
		return s;
	};

	vector<int> dp(1<<M,-1);
	dp[0]=0;

	rep(i,N-1){
		int u=A[i],v=A[i+1];
		if(u>v)swap(u,v);
		vidx[u][v].pb(i);
	}

	int ans=M;

	rep(S,1<<M){
		if(dp[S]==-1)continue;

		int r=N;

		rep(i,M){
			if(S>>i&1)continue;
			rng(j,i,M){
				if(S>>j&1)continue;
				auto it=lower_bound(all(vidx[i][j]),dp[S]);
				if(it==vidx[i][j].end())continue;
				chmin(r,*it);
				if(r==dp[S])break;
			}
			if(r==dp[S])break;
		}

		if(r==N)chmin<int>(ans,__builtin_popcount(S));
		else{
			chmax(dp[add(S,A[r])],r+1);
			chmax(dp[add(S,A[r+1])],r+2);
		}
	}

	cout<<ans<<"\n";
}

Submission Info

Judge Result