【HDOJ】2195 Monotone SE Min

 1 /* 2195 */
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 
 6 #define MAXN 1000
 7 #define MAXL 205
 8 #define INF  0xfffffff
 9 
10 int dp[MAXL][MAXN+5];
11 char s[MAXL];
12 
13 int main() {
14     int len;
15     int i, j, k;
16     int bi, tmp;
17     double ans;
18     
19     #ifndef ONLINE_JUDGE
20         freopen("data.in", "r", stdin);
21     #endif
22     
23     while (scanf("%s", s) != EOF) {
24         len = strlen(s);
25         bi = (s[0]==‘0‘) ? 0:MAXN;
26         for (j=0; j<=MAXN; ++j) {
27             dp[0][j] = (j-bi)*(j-bi);
28         }
29         for (i=1; i<len; ++i) {
30             bi = (s[i]==‘0‘) ? 0:MAXN;
31             tmp = INF;
32             for (j=0; j<=MAXN; ++j) {
33                 if (dp[i-1][j] < tmp)
34                     tmp = dp[i-1][j];
35                 dp[i][j] = tmp + (j-bi)*(j-bi);
36             }
37         }
38         tmp = INF;
39         i = len-1;
40         for (j=0; j<=MAXN; ++j)
41             if (dp[i][j] < tmp)
42                 tmp = dp[i][j];
43         ans = tmp / 1000000.0;
44         printf("%.3lf\n", ans);
45     }
46     
47     return 0;
48 }