Codeforces #626 Div1 D. Reality Show

Div1DにしてはAC数が多い。
https://codeforces.com/contest/1322/problem/D

問題

N人の演者候補から何人か選び、ショーを行う。
各人iはスキル値L[i]を持つ、また雇うときにコストS[i]がかかる。
人を選ぶ際は、番号順にスキルが非増加となるように選ばなければならない。

スキル値sの人が1人いると、ショーの開催時C[s]の利益を得る。
また、同じスキル値のひとが2人いると片方は(利益を得た後)離脱するが片方はスキル値が1上昇し、上昇後のスキル値に応じて再度利益を得る。
この手順は、スキル値が同じ2人組がいる限り繰り返し適用される。

最適な演者を雇うとき、利益-コストの最大値を求めよ。

解法

スキル値の増加は同じスキル値の人の半分までしか生じないので、同じスキル値の人が集まって増加するスキルの上限はO(logN)である。
そこでスキル値を小さい順に見て、同じスキル値の人を何人加えるか、また最後に加えたのは誰か、を状態として持ち、DPで利益の最大値を更新していこう。

int N,M;
int L[2020],S[2020];
int C[5050];

map<int,int> dp[5050];
int best[1<<12];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>L[N-1-i], L[N-1-i]--;
	FOR(i,N) cin>>S[N-1-i];
	FOR(i,N+M) cin>>C[i];
	
	int ret=0;
	FOR(i,M) {
		FOR(j,1<<12) best[j]=-1<<30;
		best[0]=0;
		
		FOR(j,N) {
			if(L[j]==i) {
				FOR(k,1<<12) if(best[k]>-1<<30) {
					int nex=best[k]-S[j];
					int nem=k;
					FOR(x,12) {
						nex+=C[L[j]+x];
						nem^=1<<x;
						if((nem&(1<<x))) {
							if(dp[j].count(nem)==0) {
								dp[j][nem]=nex;
							}
							else {
								dp[j][nem]=max(dp[j][nem],nex);
							}
							break;
						}
					}
				}
			}
			else if(L[j]<i) {
				map<int,int> ok;
				FORR(v,dp[j]) {
					if(ok.count(v.first/2)==0) {
						ok[v.first/2]=v.second;
					}
					else {
						ok[v.first/2]=max(ok[v.first/2],v.second);
					}
				}
				swap(dp[j],ok);
			}
			FORR(v,dp[j]) {
				best[v.first]=max(best[v.first],v.second);
				ret=max(ret,v.second);
			}
		}
	}
	cout<<ret<<endl;
	
}

まとめ

若干変な問題設定。