This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
“X"と”.“で構成される文字列が与えれる．"X"は壊れているフェンスを示す．全てのフェンスが壊れていない状態にしたい．区間$[i, j]$を修理したい場合は$\sqrt{j - i - 1}$かかる．全体のコストを最小化したい．
$$
dp[i] := i番目までフェンスが壊れていない状態にした時の最小コスト
$$
として動的計画法．$i$からどこまで修理するかの$j$を全探索して，更新する．その区間に"X"があって始めて修理する意味があるので，$left, right$を用意して$[i, j]$内のフェンスの最も左と右を持った．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
double dp [ 2505 ];
class FenceRepairing {
public :
double calculateCost ( vector < string > boards ) {
string s = " " ;
rep ( i , boards . size ()) {
s += boards [ i ];
}
rep ( i , 2505 ) dp [ i ] = INF ;
dp [ 0 ] = 0 ;
rep ( i , s . size ()) {
int left = - 1 , right = - 1 ;
REP ( j , i , s . size ()) {
if ( s [ j ] == 'X' ) {
if ( left == - 1 ) left = j ;
right = j ;
}
if ( left == - 1 || right == - 1 ) {
dp [ j ] = min ( dp [ j ], dp [ i ]);
} else {
dp [ j ] = min ( dp [ j ], dp [ i ] + sqrt ( right - left + 1 ));
}
}
}
return dp [ s . size () - 1 ];
}
};