首页 > ACM题库 > HDU-杭电 > hdu 2195 Monotone SE Min-动态规划-[解题报告]C++
2013
12-30

hdu 2195 Monotone SE Min-动态规划-[解题报告]C++

Monotone SE Min

问题描述 :

Given a sequence of bits (0′s and 1′s), we want to find an arbitrary monotonically increasing curve (单调递增函数)that best fits the bits. That is, the i-th bit is b(i), and we want to find some curve, f, such that for x<y, f(x) <= f(y), and the sum over i of (f(i)-b(i))^2 (the squared error)(方差) is minimized. Given the sequence of bits as a string, return the minimum possible squared error.

输入:

Multiple test cases!
For each case the input contains a string consisting of only 0 and 1 in one line. The bits string will contain between 1 and 200 elements.

输出:

Multiple test cases!
For each case the input contains a string consisting of only 0 and 1 in one line. The bits string will contain between 1 and 200 elements.

样例输入:

00
101

样例输出:

0.000
0.500

Hint: For example 1, we can make f(1) = 0,   f(2) = 0.
      For example 2, we can make f(1) = 0.5, f(2) = 0.5, f(3) = 1.

hdu 2195 Monotone SE Min 【dp】

 

题意:给定一只含01的字符串,求一个单调不减函数f,使 (f(i)-b(i))^2的和最小,1<=i<=L,其中b[i]为0或者1;

分析:显然f[i]在0到1之间。答案要求保留3位小数,因此我们可以将b[i],f[i]扩大1000倍,来进行整数运算;

令dp[i][j]表示前第i个字符时取f[i]取j时的最小值;

dp[i][j]=min{dp[i-1][k]+(j-b[i])*(j-b[i]),  1<=k<=j}

当然结果我们还有除以1000000;

复杂度: O(1000*L);

 

// hdu 2195 Monotone SE Min
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX=250;

int L;
char s[MAX];
int dp[MAX][1010];
void gs()
{
	int i,j;
	int tt=s[1]=='0'?0:1000;
	for(i=0;i<=1000;i++) dp[1][i]=(tt-i)*(tt-i);
	int small;
	for(i=2;i<=L;i++)
	{
		small=0x5fffffff;
		tt=s[i]=='0'?0:1000;
		for(j=0;j<=1000;j++)
		{
			if(small>dp[i-1][j]) small=dp[i-1][j];
			dp[i][j]=small+(tt-j)*(tt-j);
		}
	}
}
int main()
{
	while(scanf("%s",s+1)==1)
	{
		L=strlen(s+1);
		gs();

		int ans=0x5fffffff;
		for(int i=0;i<=1000;i++) ans=min(ans,dp[L][i]);
		double aa=(double)ans/1000000;
		printf("%.3lf/n",aa);
	}
	system("pause");
	return 0;
}

解题转自:http://blog.csdn.net/joy32812/article/details/5624630