SRM 325 DIV1 Easy - FenceRepairing (復習○)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=6827&rd=10005

・穴のあいたフェンスがある。
・フェンスを修理するには、sqrt(選んだ長さ)のコストが必要になる。

このとき、フェンスを修理するのに最小のコストを求める。

解き方


必ずしも、部分的に修理するのが最適解ではないと問題文にあるように、修理方法をパターン化するのは難しい。

そこで、dpを使って解く。

現在のフェンスの箇所が穴が開いていなければ前のdpと同じ答えになることから、
dp[n+1]にてdp[i]はi-1番目までのフェンスの修理コストの最小と定義する。

i番目からn番目まで走査し、0のときは前の値がないのでdp[0]=0として解いてあげればよい。

コード


class FenceRepairing {

public:

double calculateCost(vector<string> boards) {
string str="";
double INF=10000.0;

FORE(i,0,boards.size())str+=boards[i];
int n=str.size();
double dp[n+1];

FORE(i,1,n+1)dp[i]=INF;
dp[0]=0.0;

FORE(i,1,n+1){
if(str[i-1]=='.')dp[i]=dp[i-1];
else FORE(j,0,i)dp[i]=min(dp[i],dp[j]+sqrt(i-j));
}

return dp[n];
}

};
このエントリーをはてなブックマークに追加