SRM 647 DIV1 Easy - BuildingTowersEasy x

問題



http://community.topcoder.com/stat?c=problem_statement&pm=13634&rd=16279

・N個の建物を建てたい。
・建物は1からNまですべて連続していなければならなく、隣合う建物の高さの差は
1以内でなければならない。
・また、最初の建物の高さは0になる。

・加えて、x[i]番目の建物の高さはt[i]以下でなければならない。

・このとき、建物の中で最も高い建物の高さを求める。

解き方


2013 1cEasyと類似した、山の問題。

条件は以下の2つ。

・建物1は高さ0から始まって、そこからの差は1以内ずつとなる。
・各位置pについて、すべてのx[i]と比較して最大の高さはt[i]+abs(p-x[i])以内にならなければいけない。

最後に2つの条件を満たすもっとも高い建物の高さが答えになる。

コード


class BuildingTowersEasy {

public: int maxHeight(int N, vector<int> x, vector<int> t) {
int d[N+1];
for(int i=1;i<=N;i++)d[i]=i-1;

for(int i=1;i<=N;i++){
FORE(j,0,x.size()){
d[i]=min(d[i],t[j]+abs(i-x[j]));
}
}

return *max_element(d+1,d+1+N);
}

};

Share this

Related Posts

Previous
Next Post »