Codeforces #708 Div2 : D. Genius

あいにく全完できず…。
https://codeforces.com/contest/1497/problem/D

問題

N個の問題がある。
i問目の難易度はC[i]=2^iである。
また、各問題のスコアS[i]と種別T[i]が与えられる。

パラメータIQの初期値を0とする。
最初は任意の問題を解くことができる。
2問目以降、直前にi問目を解いた次にj問目を解く場合、以下の条件を満たす必要がある。

• T[i]!=T[j]
• IQ＜|C[i]-C[j]|

また、解いた後はIQ=|C[i]-C[j]|となり、|S[i]-S[j]|のスコアを得る。

最適な問題の解き順を選ぶとき、総スコアの最大値を求めよ。
なお、メモリは(N^2)個のint配列を取る容量はない。

解法

IQに関する条件より、1問目から2問目に至る場合のみi＞jと遷移できるが、以後はi＜jでなければならない。
dp(n) := 今まで選んだ問題の選択順の最後がn番目である場合、そこまでのスコアの最大値
とする。
1問目と2問目を総当たりしながらdp(n)を更新していこう。

int T,N,A[5050],S[5050];

ll dp[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		FOR(i,N) cin>>S[i];
		FOR(i,N+1) dp[i]=-1LL<<60;
		
		ll ret=0;
		FOR(i,N) {
			ll ma=0;
			for(j=i-1;j>=0;j--) if(A[i]!=A[j]) {
				ll nma=ma+abs(S[i]-S[j]);
				ma=max(ma,dp[j]+abs(S[i]-S[j]));
				dp[j]=max(dp[j],nma);
			}
			dp[i]=ma;
		}
		FOR(i,N) ret=max(ret,dp[i]);
		cout<<ret<<endl;
	}
}

まとめ

ループの回し順をいかに思いつけるかという問題。