Codeforces #939 : Div2 D. Nene and the Mex Operator

systestで落ちるとげんなりしてしまうなぁ。
https://codeforces.com/contest/1956/problem/D

問題

整数列Aが与えられる。
Aの部分列をA[L,R]を指定し、A[L,R]をmex(A[L,R])に同時に更新することを考える。
Aの最大値とそれを実現する手段を求めよ。

解法

ある区間に対し、A[L,R]を0,1,2,3...(R-L)とすることができる。
これはA[L,R-1]を0,1,2,3...(R-L-1)にすることが出来ることから再帰的に可能。

あとはDPで、区間に対しA[L,R]=0,1,2,3....に置き換えた方が得かどうかを求めよう。

int N;
int A[20];

ll dp[20];
int from[20];

vector<pair<int,int>> ret;

void dfs(int L,int R) {
	if(L+1==R) return;
	dfs(L,R-1);
	ret.push_back({L,R-1});
	ret.push_back({L,R-2});
	dfs(L,R-1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	FOR(i,N+1) dp[i]=-1;
	dp[0]=0;
	FOR(i,N) {
		if(dp[i]+A[i]>dp[i+1]) {
			dp[i+1]=dp[i]+A[i];
			from[i+1]=i;
		}
		for(x=i+1;x<=N;x++) {
			if(dp[x]<dp[i]+(x-i)*(x-i)) {
				dp[x]=dp[i]+(x-i)*(x-i);
				from[x]=i;
			}
		}
	}
	
	int cur=N;
	while(cur) {
		x=from[cur];
		if(A[x]==0||cur-x>1) {
			for(j=x;j<cur;j++) if(A[j]==0) break;
			if(j==cur) {
				ret.push_back({x,cur-1});
			}
			else {
				ret.push_back({x,cur-1});
				ret.push_back({x,cur-1});
			}
			dfs(x,cur);
			ret.push_back({x,cur-1});
		}
		cur=x;
	}
	
	cout<<dp[N]<<" "<<ret.size()<<endl;
	FORR2(a,b,ret) cout<<a+1<<" "<<b+1<<endl;
	
}

まとめ

A	が20なので、最初bitDPを考えてしまった。