問題はこちら
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); }