Codeforces #870 : Div2 E. Walk the Runway

Dまで簡単だけどEから急に難易度が上がる。
https://codeforces.com/contest/1826/problem/E

問題

N人のモデルがおり、M個の地域で彼らを引き連れてツアーを行う。
各地域はモデルの好みがある。
N人のうちK人を選び、その登場順を定めたとする。

各地域において、各人が好みが登場順に昇順となるように定めなければならない。
各モデルを選んだ場合の価値が与えられる場合、価値の総和を最大化せよ。

解法

bitsetで、各人と同時に選べない人の集合を求めて行く。

int M,N;
int P[5050];
ll dp[5050];
int R[5050];
bitset<5120> NG[5050],E;
vector<int> C[5050];


void solve() {
	int i,j,k,l,r,x,y; string s;
	scanf("%d%d",&M,&N);
	FOR(i,N) {
		scanf("%d",&P[i]);
	}
	FOR(y,M) {
		FOR(x,N) C[x].clear();
		FOR(x,N) {
			scanf("%d",&R[x]);
			C[R[x]-1].push_back(x);
		}
		E.reset();
		for(x=N-1;x>=0;x--) {
			FORR(a,C[x]) E[a]=1;
			FORR(a,C[x]) NG[a]|=E;
		}
	}
	vector<pair<int,int>> V;
	FOR(i,N) V.push_back({R[i],i});
	sort(ALL(V));
	
	ll ma=0;
	FORR2(a,i,V) {
		dp[i]=0;
		FOR(x,N) {
			if(NG[i][x]==0) dp[i]=max(dp[i],dp[x]);
		}
		dp[i]+=P[i];
		ma=max(ma,dp[i]);
	}
	cout<<ma<<endl;
	
	
}

まとめ

ちょっと力技。