SRM547 Div2 Medium(500) PillarsDivTwo

TopCoder

PillarsDivTwo

動的計画法。それぞれの塔のそれぞれの位置にロープを付ける場合の、そこまでのロープの最大の長さを覚えておく。

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

class PillarsDivTwo{public:
double maximalLength( vector <int> height, int w )
{
    vector<vector<double> > T(1,vector<double>(height[0]+1));

    for ( int i=1; i<(int)height.size(); i++ )
    {
        T.push_back(vector<double>(height[i]+1));

        for ( int j=1; j<(int)T[i-1].size(); j++ )
        for ( int k=1; k<(int)T[i  ].size(); k++ )
            T[i][k] = max(T[i][k],T[i-1][j]+hypot(j-k,w));
    }

    return *max_element(T.back().begin()+1,T.back().end());
}};