読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #393 Div1 B. Travel Card

Codeforces

なんか今回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;
	}
	
}

まとめ

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

広告を非表示にする