メモ

yukicoderでゆるふわgolf

yukicoder No.561 東京と京都

問題はこちら
No.561 東京と京都 - yukicoder

DPやるだけ(といいつつ、後ろから見る方法しか思いつかなかったので要反省)

(i-1)日目が終了した時点で東京にいるときの最大利益をT、京都にいるときの最大利益をKとおく。
i日目に東京でt、京都でk得られる場合
i日目が終了した時点で東京にいるときの最大利益はmax(T,K-d)+t、京都にいるときの最大利益はmax(K,T-d)+kとなる。
これによりK,Tを順次更新していけば良い。
初期値はT=0、K=-dとなる。(1日目が始まる前に京都へ移動したと考える)

T,K,t,k,n,d;
main(){
	scanf("%d%d",&n,&d);
	K=-d;
	for(int i=0;i<n;i++){
		scanf("%d%d",&t,&k);
		t=fmax(T,K-d)+t;
		k=fmax(K,T-d)+k;
		T=t;
		K=k;
	}
	printf("%d",T>K?T:K);
}

数値は2個1セットで読み込めるので次のようにできる

T,K,t,k,d;
main(i){
	for(;~scanf("%d%d",&t,&k);){
		if(--i){
			t=fmax(T,K-d)+t;
			k=fmax(K,T-d)+k;
			T=t;
			K=k;
		}else{
			d=k;
			K=-d;
		}
	}
	printf("%d",T>K?T:K);
}

これをぎゅっとする

T,K,t,k,d;
main(i){
	for(;~scanf("%d%d",&t,&k);)K=--i?k+=fmax(K,T+d),T=t+fmax(T,K+d),k:(d=-k);
	printf("%d",T>K?T:K);
}