PKU 2313 Sequence
http://poj.org/problem?id=2313
ある数列Aが与えられる。
このとき、与えられた計算式の結果が最小になるような数列Bを見つけて、最小値を答えろというような問題。
なんとなくこれでいけないかと思ったら、いけた問題。
証明は試みていません。
int in[100]; int b[100]; main(){ int n; cin>>n; rep(i,n)cin>>in[i]; b[0]=in[0]; for(int i=1;i<n-1;++i){ PI p=mp(min(in[i],b[i-1]),max(in[i],b[i-1])); if(p.F<=in[i+1] && in[i+1]<=p.S)b[i]=in[i+1]; else if(in[i+1]<p.F)b[i]=p.F; else b[i]=p.S; } b[n-1]=in[n-1]; int ans=0; rep(i,n)ans+=abs(b[i]-in[i]); rep(i,n-1)ans+=abs(b[i]-b[i+1]); cout<<ans<<endl; }