首页 > ACM题库 > HDU-杭电 > HDU 3276-Star-动态规划-[解题报告]HOJ
2014
03-13

HDU 3276-Star-动态规划-[解题报告]HOJ

Star

问题描述 :

One of Resty’s interests is to watch stars. The Stars are so beautiful! Lyra’s Vega, Alpha Aquila – Altair and Alpha Cyg consist of the Summer Triangle. Resty likes them very much.
One day, Resty comes to the Moon to have his picnic. Soon he found that he can see so many beautiful stars here! You can never find such a view again – All the beautiful stars are in one line!! So Resty wants to take photos to record the incredible moment.
Resty likes those stars so much so he knows which one is more beautiful. Now he gives each star a score, (a number between 1 and 200000, the higher, the better). So we can use an integer sequence to show the stars from left to right.
Resty’s camera is very strange and it will take two photos at one time, and each photo will contain a series of continuous stars in it. No stars will appear in both photos, and even no two stars that adjacent to each other will be in different photos. The number of stars in each photo will between x and y.
Now, Resty tells you the sequence, you must find two photos that the average score of all the stars in the photos is as great as possible.

输入:

The input consists of more than one test case.
Process to the END OF DATA.
For each test case:
The first line contains 3 integers: n, x, y. n is the number of stars.
1 <= x < y <= n <=50000
The second line contains n integers (between 1 and 200000), the score of each stars.

输出:

The input consists of more than one test case.
Process to the END OF DATA.
For each test case:
The first line contains 3 integers: n, x, y. n is the number of stars.
1 <= x < y <= n <=50000
The second line contains n integers (between 1 and 200000), the score of each stars.

样例输入:

5 1 2
1 2 3 4 5
6 2 3
6 1 2 4 3 5

样例输出:

Case 1: 4.000
Case 2: 3.800

Problem from:http://acm.hdu.edu.cn/showproblem.php?pid=3276

在一个数列中寻找两个不相交且不相邻长度为Len(x<=Len<=y)的连续子序列,使这两个子数列的平均数最大,求该最大平均数

最大平均数用二分搜索来求

每次二分搜索一个值k,判断是否存在这样的两个子序列的平均值大于等于k,存在则向上二分搜索,不存在则向下搜索

如何判断一个数列的平均值与k的大小关系:把每个数减去k,再求所有数的和(此处的和假设用Ek表示)

DP在该处的运用:DP[i]用来存储数列前 i 个数中,所有 长度为Len(x<=Len<=y)的连续子序列 中 最大的Ek(Ek:上一行有定义)

剩下的我们就只要枚举原数列下标i(x<i,i+x<=n)

判断    第1..到..第i-1的数列中 满足长度子序列 最大的Ek    与    第i+1..到..第n的数列中 满足长度子序列 最大的Ek    的和是否>=0

最后剩下的就是如何实现DP了:

DP前,先用一个数组sum[],sum[i]存前 i 个数的 Ek

假设DP[i-1]已实现,则DP[i]=max(DP[i-1]  ,  max(sum[i]-sum[j] (x<= i-j <=y) )  )

这时用的技巧就是用双端队列快速求 max(sum[i]-sum[j] (x<= i-j <=y) )//i-y<= j <=i-x

每次求DP[i]时,向双端队列末端加入sum[]下标i-x

在 向双端队列末端加入sum[]下标i-x 前,判断双端队列末端的元素s,sum[s]是否>sum[i-x],是则弹出该s,直到队列为空或者不存在sum[s]>s[i-x] 再加入i-x

然后判断双端队列首端的元素s,s是否<i-y,是则弹出该s,直到队列中不存在<i-y的s

这样的操作可以保证双端队列中的元素s全部满足(i-y<=s<=i-x)且 从首端到末端 的sum[s]是呈递增的

此时就可以判定DP[i]=max(DP[i-1],sum[i]-sum[s](s为双端队列首端的元素))

Star

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=50010;
int a[MAXN],n,x,y,Case;
double sum[MAXN],Ldp[MAXN],Rdp[MAXN];//sum[i]存前i个数的Ek;Ldp[i]存前i个数中 满足长度的子序列 中的最大Ek;Rdp[i]存第i个数到第n个个数中 满足长度的子序列 中的最大Ek
bool f(double dt){
    sum[0]=0;
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]-dt;
    deque<int> que;
    Ldp[x-1]=-1e10;
    for(int i=x;i<n-x;i++){//求Ldp[]
        while(!que.empty() && sum[i-x]<sum[que.back()])
            que.pop_back();
        que.push_back(i-x);
        while(que.front()<i-y)
            que.pop_front();
        Ldp[i]=max(Ldp[i-1],sum[i]-sum[que.front()]);
    }
    que.clear();
    sum[n+1]=0;
    for(int i=n;i>0;i--)sum[i]=sum[i+1]+a[i]-dt;
    Rdp[n-x+2]=-1e10;
    for(int i=n-x+1;i>x;i--){//求Rdp[],原理和求Ldp[]一样
        while(!que.empty() && sum[i+x]<sum[que.back()])
            que.pop_back();
        que.push_back(i+x);
        while(que.front()>i+y)
            que.pop_front();
        Rdp[i]=max(Rdp[i+1],sum[i]-sum[que.front()]);
    }
    for(int i=x+1;i<=n-x;i++)//枚举判断
        if(Ldp[i-1]+Rdp[i+1]>=0)return true;
    return false;
}
void work(){
    double L=1,R=200000,ans;
    while(R-L>1e-5){
        ans=(L+R)/2;//二分搜索最大平均值
        if(f(ans))L=ans;
        else R=ans;
    }
    printf("Case %d: %.3lf\n",++Case,ans);
}
int main()
{
    while(scanf("%d%d%d",&n,&x,&y)!=EOF){
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        work();
    }
    return 0;
}

View Code

后来,我用优先队列(编码会简单些)来实现,时间复杂度还是高了点,超时。

双端队列和队列一样是可以用数组来实现的,尤其是像这样的每个元素最多入队一次出队一次的题,实现起来没压力

参考:http://www.cnblogs.com/cshhr/p/3540957.html


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  3. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!