HTML头标签<meta>使用-重新定向，refresh

2020-12-10 08:18

阅读：477

标签：dp 单调队列

链接：http://acm.hdu.edu.cn/showproblem.php?pid=3415

题意：给出一个数环，要找出其中9长度小于等于K的和最大的子段。

思路：不能采用最暴力的枚举，题目的数据量是10^5，O(N^2)的枚举回去超时，本题采用的很巧妙的DP做法，是用单调队列优化的DP。

运用的是STL的deque，从i:1~a找到以其中以i为尾的符合条件的子段，并将i本身放入双向队列，所有i从队列后放入，保证了队列的单调性。

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define maxn 100005*2
#define maxm
#define INF 0x7fffffff
typedef long long ll;
using namespace std;
int num[maxn],sum[maxn];
int main()
{
    int tot;
    scanf("%d",&tot);
    while(tot--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        scanf("%d",&num[1]);
        sum[1]=num[1];
        for(int i=2;i dd;
        int ans=-INF,head=-1,tail=-1;
        for(int i=1;idd.front()+b)
            dd.pop_front();
            dd.push_back(i-1);
            if(sum[i]-sum[dd.front()]>ans)
            {
                ans=sum[i]-sum[dd.front()];
                head=dd.front()+1;
                tail=i;
            }
        }
        if(head>a)
        head-=a;
        if(tail>a)
        tail-=a;
        printf("%d %d %d\n",ans,head,tail);
    }
    return 0;
}

HTML头标签使用-重新定向，refresh

标签：dp 单调队列

原文地址：http://blog.csdn.net/hymking/article/details/24820951

上一篇：ASP.NET MVC 5 入门指南汇总

下一篇：HTML的表单form以及form内部标签

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：HTML头标签<meta>使用-重新定向，refresh
文章链接：http://soscw.com/essay/23607.html

亲，登录后才可以留言！

HTML头标签<meta>使用-重新定向，refresh

评论

热门文章

推荐文章

最新文章

置顶文章

HTML头标签&lt;meta&gt;使用-重新定向，refresh

评论

热门文章

推荐文章

最新文章

置顶文章

HTML头标签<meta>使用-重新定向，refresh