Codeforces #393 Div1 B. Travel Card

なんか今回Writerが豪華な割に普通な問題が多い？
http://codeforces.com/contest/759/problem/B

問題

N要素からなる単調増加な数列T[i]が与えられる。
各1≦x≦Nに対し、以下の3つを使いT[1]～T[x]を覆い切るコストの最小値を求めよ。

• 整数1つを覆う。コスト20。
• 連続する整数90個を覆う。コスト50。
• 連続する整数1440個を覆う。コスト120。

解法

f(x) := T[1]～T[x]を覆う最小コスト
とする。
f(x-1)まで決まったとすると以下の要領で最小値を更新して行けばよい。

• f(x) = min(f(x), f(x-1)+20)
• f(y) = min(f(y), f(x-1)+50) (T[y]-T[x]＜90)
• f(z) = min(f(z), f(x-1)+120) (T[z]-T[x]＜1440)

int N;
int T[101010];
ll ret[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) {
		cin>>T[i];
		ret[i]=1LL<<60;
	}
	for(i=1;i<=N;i++) {
		ret[i]=min(ret[i],ret[i-1]+20);
		for(j=i+1;j<=N && T[j]-T[i]<90;j++) ret[j]=min(ret[j],ret[i-1]+50);
		for(j=i+1;j<=N && T[j]-T[i]<1440;j++) ret[j]=min(ret[j],ret[i-1]+120);
		cout<<ret[i]-ret[i-1]<<endl;
	}
	
}

まとめ

この問題なんなんだろう…。