Codeforces ECR #087 : F. Summoning Minions

復元めんどいなぁ。
https://codeforces.com/contest/1354/problem/F

問題

N体のキャラクターがおり、そのキャラを任意順で召喚または破壊できる。
ただし、

• 各キャラクターは1回までしか召喚できない。
• 召喚済みで未破壊のキャラクターがK体を超える瞬間があってはならない。

各キャラiのパワーの初期値はA[i]である。
また、キャラiを召喚すると、召喚済みキャラのパワーがB[i]だけ増加する。

最終的に召喚済みキャラの総パワーが最大化するよう、適切なキャラの召喚・破壊順を求めよ。

解法

まず、召喚済みキャラが多いほどB[i]の多さが活きるので、最終的に残すキャラの召喚順はB[i]の昇順である。
それ以外のキャラについては、(K-1)体キャラがそろった段階で召喚して即破壊するのが良い。

これを踏まえて、キャラをB[i]に並べたうえで、最終的に残すものと残さないものを選び、DPで最終的な総パワーの最大値を求めよう。
最後にそのDPを復元し、召喚・破壊順を定める。

int T;
int N,K;
pair<int,int> P[101];

int A[76],B[76];
pair<ll,int> from[76][76];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,N) {
			cin>>A[i]>>B[i];
			P[i]={B[i],i};
		}
		sort(P,P+N);
		
		FOR(x,76) FOR(y,76) from[x][y]={-(1LL<<60),0};
		from[0][0]={0,0};
		FOR(x,N) {
			FOR(y,N+1) if(from[x][y].first>=0) {
				// take
				if(y<N) {
					ll v=from[x][y].first+A[P[x].second]+P[x].first*y;
					if(from[x+1][y+1].first<v) from[x+1][y+1]={v,1};
				}
				// not take
				{
					ll v=from[x][y].first+P[x].first*(K-1);
					if(from[x+1][y].first<v) from[x+1][y]={v,0};
				}
			}
		}
		
		vector<int> X,Y;
		x=N,y=K;
		while(x>0) {
			if(from[x][y].second==0) {
				Y.push_back(1+P[x-1].second);
			}
			else {
				X.push_back(1+P[x-1].second);
				y--;
			}
			x--;
		}
		reverse(ALL(X));
		cout<<Y.size()*2+X.size()<<endl;
		FOR(i,X.size()-1) cout<<X[i]<<" ";
		FOR(i,Y.size()) cout<<Y[i]<<" "<<-Y[i]<<" ";
		cout<<X.back()<<endl;
		
	}
}

まとめ

最大値求めるだけじゃダメだったのかなぁ…。