SRM 647 Div2 1000 BuildingTowers

問題概要
N個のビルがあり、ラベルが1からNまで振られている。
以下の条件を満たすとき、ビルNの高さの最大値を求めよ。

• ビル1の高さは0
• すべてのビルの高さは非負整数
• 隣り合うビルの高さの差はK以下
• ビルx[i]の高さはt[i]以下

解法
与えられたx[]のビルについて、最大の高さを求める。
このとき、前から見たときと、後ろから見たときに、3つ目の条件を満たすように最大の高さを計算しないといけない。
x[]のビルについて決まったら、x[i]とx[i+1]の間の区間に立てられるビルの最大の高さを求める。これをすべてのiについて行う。

後ろから見たときのチェックは見落としがちなので、注意が必要。

実装

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

const long long oo = 1LL<<60;

class BuildingTowers {
  public:
  long long maxHeight(int N, int K, vector<int> x_, vector<int> t_) {
    vector<long long> x(ALL(x_));
    vector<long long> t(ALL(t_));

    if (x.size() && x[0] == 1) t[0] = 0;
    else {
      x.insert(x.begin(), 1);
      t.insert(t.begin(), 0);
    }

    int m = x.size();
    for (int i = 1; i < m; i++)
      t[i] = min(t[i], t[i-1] + K * (x[i] - x[i-1]));
    for (int i = m-2; i >= 0; i--)
      t[i] = min(t[i], t[i+1] + K * (x[i+1] - x[i]));
    
    long long ret = 0;
    REP (i, m-1) {
      long long z = (t[i+1] - t[i] + K * (x[i] + x[i+1])) / (2 * K);
      if (x[i] <= z && z <= x[i+1])
        ret = max(ret, t[i] + K * (z - x[i]));
      ++z;
      if (x[i] <= z && z <= x[i+1])
        ret = max(ret, t[i+1] + K * (x[i+1] - z));
    }
    ret = max(ret, t[m-1] + K * (N - x[m-1]));
    return ret;
  }
};