SRM 647 DIV1 Easy - BuildingTowersEasy x
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13634&rd=16279
・N個の建物を建てたい。
・建物は１からNまですべて連続していなければならなく、隣合う建物の高さの差は
１以内でなければならない。
・また、最初の建物の高さは０になる。
・加えて、x[i]番目の建物の高さはt[i]以下でなければならない。
・このとき、建物の中で最も高い建物の高さを求める。
解き方
2013 1cEasyと類似した、山の問題。
条件は以下の２つ。
・建物１は高さ０から始まって、そこからの差は１以内ずつとなる。
・各位置pについて、すべてのx[i]と比較して最大の高さはt[i]＋abs(p-x[i])以内にならなければいけない。
最後に２つの条件を満たすもっとも高い建物の高さが答えになる。
コード
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);
}
};
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);
}
};
