本文主要是介绍HDU 4923 Room and Moor【栈】【想法】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=4923
题目大意：给你一串A = {A1, A2,..., AN}由{0,1}组成， 你要构造出一字符串 B = {B1, B2,... , BN}与A的长度相同。
求出这个最小值。
最开始见到这个题目先是想了想应该怎么做，比如先把A串处理一下。
1）把A前面的0去掉
2）把A后面的1去掉
3）将每部分的特值算出来。
举个栗子吧，字符串A将前的0去掉，后面的1去掉之后，字符串可以简化为N个 {1..1 0...0} 组成的单位。
比如组成之后是这样的
10 110 10 1110 每部分取到最小值的时候x取值分别为 假设每组有a个1，b个0，则每组取到最小值时x取值是a/(a+b)
x1 x2 x3 x4
1/2 2/3 1/2 3/4
如果其x的值是一个递增的就好了，思路在这就断了....... 甚至还想到了最大上升子串......还是无果.......
赛后看解题报告，其实想法还是不够，差了最后一步。
我们这样来想
下面的思路就通了，我们将过程模拟成栈，那么扫描入栈一个我们就判断它求的x与栈顶的值时候满足非递减的关系，不是的话我们合并，处理完后求值就行了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;double num[maxn], len[maxn];
//num[i]表示该区间1的个数，len[i]表示该区间的长度int main()
{int t, n;scanf("%d", &t);while (t--){scanf("%d", &n);int cnt = 0, a;for (int i = 0; i < n; i++){scanf("%d", &a);num[cnt] = a;len[cnt ++] = 1;while (cnt >= 2){if (num[cnt-1]/len[cnt-1] > num[cnt-2]/len[cnt-2])break;num[cnt-2] += num[cnt-1];len[cnt-2] += len[cnt-1];cnt--;}}double ans = 0.0;for (int i = 0; i < cnt; i++){double tmp = num[i]/len[i];ans += tmp*tmp*(len[i]-num[i]) + (1-tmp)*(1-tmp)*num[i];}printf("%.6lf\n", ans);}return 0;
}
这篇关于HDU 4923 Room and Moor【栈】【想法】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
