简单DP。将[0,1]的浮点数离散化为[0,1000]的整数。最后再除以1000^2.
/* 2195 */
#include <cstdio>
#include <cstring>
#include <cstdlib> #define MAXN 1000
#define MAXL 205
#define INF 0xfffffff int dp[MAXL][MAXN+];
char s[MAXL]; int main() {
int len;
int i, j, k;
int bi, tmp;
double ans; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif while (scanf("%s", s) != EOF) {
len = strlen(s);
bi = (s[]=='') ? :MAXN;
for (j=; j<=MAXN; ++j) {
dp[][j] = (j-bi)*(j-bi);
}
for (i=; i<len; ++i) {
bi = (s[i]=='') ? :MAXN;
tmp = INF;
for (j=; j<=MAXN; ++j) {
if (dp[i-][j] < tmp)
tmp = dp[i-][j];
dp[i][j] = tmp + (j-bi)*(j-bi);
}
}
tmp = INF;
i = len-;
for (j=; j<=MAXN; ++j)
if (dp[i][j] < tmp)
tmp = dp[i][j];
ans = tmp / 1000000.0;
printf("%.3lf\n", ans);
} return ;
}