CODE THANKS FESTIVAL 2018 : G - Sum of Cards

600ptでもいいかも？
https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_g

問題

N枚のカードが与えられる。
各カード両面に数字が書いてあり、表面N枚で1～N、裏面N枚で1～Nが1回ずつ登場する。

ここで、各カードを表裏任意の向きを上に向けることができるとする。
上を向いた数字の種類がK以上あるような組み合わせのうち、総和の最大値を求めよ。

解法

1～Nに相当するN個の頂点を考える。
ここで、各カード(表面の数字)→(裏面の数字)に対して有向辺を張ると、N頂点がいくつかのサイクルになる。

そこで、各サイクルにおいて、何個の数字を選択すると総和の最大値がどうなるか、という値を求め、DPの要領で全サイクルにおける選択した数字の総和と、全カードの総和の最大値を求めていく。

各サイクルにおいては、各有効辺に対して、両端のどちらかの数字を選択するということを繰り返すことになる。
円周上のDPの典型例として、ある1要素を選択した・しない場合を仮定し、そこから辺のつながる各要素に対し、辺のどちら側を選択したか、およびこれまで選択したユニークな数字の数を状態としてDPしていけばよい。

int N,K;
int A[5050],B[5050];
int P[5050];
int vis[5050];

int from[5050],to[5050],dp[5050];
int tdp[5050][5050][2];

void hoge(vector<int> V) {
	int i,x,y;
	int M=V.size();
	FOR(i,M+1) dp[i]=-1<<30;
	
	if(M==1) {
		dp[1]=V[0];
		return;
	}
	V.push_back(V[0]);
	
	FOR(i,2) {
		FOR(x,M+1) FOR(y,M+1) tdp[x][y][0]=tdp[x][y][1]=-1<<30;
		
		if(i==0) tdp[0][1][1]=V[1];
		if(i==1) tdp[0][1][0]=V[0];
		
		for(x=1;x<M;x++) {
			for(y=1;y<M;y++) {
				tdp[x][y][0]=max(tdp[x][y][0],tdp[x-1][y][1]+V[x]);
				tdp[x][y+1][0]=max(tdp[x][y+1][0],tdp[x-1][y][0]+V[x]);
				tdp[x][y+(x<M-1||i==0)][1]=max(tdp[x][y+(x<M-1||i==0)][1],tdp[x-1][y][1]+V[x+1]);
				tdp[x][y+(x<M-1||i==0)][1]=max(tdp[x][y+(x<M-1||i==0)][1],tdp[x-1][y][0]+V[x+1]);
			}
		}
		for(x=1;x<=M;x++) dp[x]=max({dp[x],tdp[M-1][x][0],tdp[M-1][x][1]});
	}
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	FOR(i,N) {
		cin>>B[i];
		P[A[i]]=B[i];
	}
	
	FOR(x,5005) from[x]=-1<<30;
	from[0]=0;
	int cur=0;
	
	for(i=1;i<=N;i++) if(vis[i]==0) {
		vector<int> V;
		V.push_back(i);
		x=P[i];
		while(x!=i) {
			V.push_back(x);
			x=P[x];
		}
		FORR(v,V) vis[v]=1;
		
		hoge(V);
		
		FOR(x,5050) to[x]=-1<<30;
		
		FOR(x,cur+1) FOR(y,V.size()+1) to[x+y]=max(to[x+y],from[x]+dp[y]);
		cur+=V.size();
		swap(from,to);
	}
	
	int ret=0;
	for(i=K;i<=N;i++) ret=max(ret,from[i]);
	cout<<ret<<endl;
	
}

まとめ

最初最小コストフロー書いたらTLEした。