Hack Everything DP 考察 SRM 325 DIV1 Easy - FenceRepairing

SRM 325 DIV1 Easy - FenceRepairing

問題

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

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

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

解き方

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

そこで、ｄｐを使って解く。

現在のフェンスの箇所が穴が開いていなければ前のｄｐと同じ答えになることから、
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];
}

};

Share this

Google Facebook Twitter More