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を考えてしまった。 |