SRM 547 Div2 Medium PillarsDivTwo

問題

水平な地面にN個の柱がW間隔ごとに立っている.i番目の柱の高さは1〜height[i]のいずれかで表される.隣接する柱のてっぺんをロープで繋ぐ場合を考える.たるみなくロープを張った時必要なロープの最大の長さを求めよ.

解答

DPを使う.i番目の柱の高さをXとした時の1〜iまでの最適値をDP[i][X]とすると,DP[i][X]はDP[i-1]から計算することが出来る.高さの範囲が狭いので余裕で計算できる.

他人のソースコードを見て気づいた.三平方の定理を計算する関数があるんだね
hypot - C++ Reference

class PillarsDivTwo
{
public:
  double maximalLength(vector <int> height, int w)
    {
      int n = height.size();
      vector<vector<double> > dp(n, vector<double>(101, 0));
      for(int i = 1; i < n; i++){
        for(int k = 1; k <= height[i]; k++){
          for(int j = 1; j <= height[i-1]; j++){
            double v = w;
            if (k != j){
              v = sqrt((double)w * w + (k-j)*(k-j));
            }
            dp[i][k] = max(dp[i][k], dp[i-1][j] + v);
          }
          // cout << "(i, k)=(" << i << ", " << k << ")";
          // cout << dp[i][k] << endl;
        }
      }
      double res = 0;
      for(int i = 1; i <= height[n-1]; i++){
        res = max(res, dp[n-1][i]);
      }
      return res;
    }
};