Codeforces #854 : D2. Hot Start Up (hard version)

出来がちょっと悪かった回。
https://codeforces.com/contest/1799/problem/D2

問題

K種類のプログラムがあり、それぞれCPUが冷たい場合と温かい場合にかかる時間が与えられる。
また、N要素の数列が与えられ、これは実行するプログラムの順番を示す。

CPUは、直前に実行したプログラムと同じプログラムを動かす場合、温かい状態で実行できる。そうでない場合冷たい場合となる。

計N回プログラムを順に実行するが、これらを2つのCPUを使って行う。
各プログラムをどのCPUで行うかを任意に選択できる場合、全プログラムを実行し終わるまでにかかる最小どれだけ時間がかかるかを求めよ。

解法

dp(n,k) := n回目までプログラムを実行した場合、片方のCPUはn回目のもの、もう片方のCPUはk種類目のプログラムを実行した状態であるような状態における最小時間
とすると、dp(n,*)→dp(n+1,*）の状態遷移は全体に同じ値を加算するのがほとんどであり、O(1)で値の変化を表現できる。

int T,N,K;
int A[303030];
int C[303030],H[303030];

ll V[303030];
ll D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&N,&K);
		FOR(i,N) scanf("%d",&A[i]);
		FOR(i,K) scanf("%d",&C[i+1]);
		FOR(i,K) scanf("%d",&H[i+1]);
		
		D=0;
		
		FOR(i,K+1) {
			if(i==0) {
				V[i]=C[A[0]];
			}
			else {
				V[i]=1LL<<50;
			}
		}
		ll miv=V[0];
		
		for(i=1;i<N;i++) {
			//全体更新
			ll a=(A[i]==A[i-1])?H[A[i]]:C[A[i]];
			ll mi=min(D+miv+C[A[i]],D+V[A[i]]+H[A[i]]);
			
			D+=a;
			ll b=V[A[i-1]]+D;
			if(mi<b) {
				V[A[i-1]]=mi-D;
				miv=min(miv,V[A[i-1]]);
			}
		}
		_P("%lld\n",D+miv);
	}
}

まとめ

SegTreeとか使った方が考察は楽だったかも？