POJ3017 Cut the Sequence(单调队列优化dp)好题!!必做!!

Cut the Sequence POJ - 3017

Given an integer sequence { an } of length N, you are to cut the sequence into several parts every one of which is a consecutive subsequence of the original sequence. Every part must satisfy that the sum of the integers in the part is not greater than a given integer M. You are to find a cutting that minimizes the sum of the maximum integer of each part.
Input
The first line of input contains two integer N (0 < N ≤ 100 000), M. The following line contains N integers describes the integer sequence. Every integer in the sequence is between 0 and 1 000 000 inclusively.

Output
Output one integer which is the minimum sum of the maximum integer of each part. If no such cuttings exist, output −1.
Sample Input
8 17
2 2 2 8 1 8 2 1
Sample Output
12
Hint
Use 64-bit integer type to hold M.

题意

在一个长度为n的序列中,切割每段的代价是这段中最大元素的值,且任意一段的和不能超过m,求一种分割方式使得每部分的最大值的sum最小,求出这个最小值。(我说清楚了么…看不懂的请继续往下看…)

思路

用dp[i]表示到第i个元素的最小花费
很明显我门可以得到这样一个状态转移方程
dp[i]=min(dp[j]+max(a[j+1],a[j+2],…a[i]))&&sum[i]-sum[j]<=m;
太好了,很明显我们需要用一个单调队列来维护这个j
请看代码

#include<algorithm>
#include "cstdio"
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
#define maxn 100005
ll dp[maxn],a[maxn],q[maxn],sum[maxn];
int main(){
    ll n,m;
    scanf("%lld%lld",&n,&m);
    bool flag=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        if(a[i]>m)flag=1;
    }
    if(flag){
        printf("-1\n");
    }else{
        int head,tail;
        head=1;tail=1;
        int index=1;
        ll sum=0;//区间和
        for(int i=1;i<=n;i++){
            //队尾元素小于当前元素就要出队,为什么呢,以为我们当前要塞进去的元素比队尾那个元素更大,那么我们这个区间的最大值肯定不会选择那个元素,我们现在塞进去的肯定是一个更优解,那个元素就没有必要呆在队列里面 
            while(head<tail&&a[q[tail]]<=a[i])tail--;
            sum+=a[i];
            q[tail++]=i;//请注意我们队列存的是下标
            //这里要保证队列的合法性,index是合法的第一个元素
            while(sum>m)sum-=a[index++];
            while(q[head]<index)head++;//队列对头下标要满足要求
            dp[i]=dp[index-1]+a[q[head]];//先给当前dp赋值
            for(int j=head+1;j<tail;j++)//扫一遍当前队列,体会一下这个循环
                //dp[i]=min(dp[j]+max(a[j+1].....a[i]));
                dp[i]=min(dp[i],dp[q[j-1]]+a[q[j]]);
        }
        printf("%lld\n",dp[n]);
    }
    
    return 0;
}

/*
 8 17
 2 2 2 8 1 8 2 1
 12
 */

全部评论
这样会被卡掉只是数据水而已
点赞 回复 分享
发布于 2024-02-20 08:39 浙江

相关推荐

不愿透露姓名的神秘牛友
07-11 17:10
什么素质,我请问呢,要掉小珍珠了。。。又憋屈又生气
苍蓝星上艾露:给它们能的,一群dinner牛马挥刀向更弱者罢了。我写的开源求职AI co-pilot工具,优化你的简历,找到你匹配的岗位,定制你的简历,并让你做好面试准备https://github.com/weicanie/prisma-ai
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-11 11:24
大家还是用ai改吧,我心疼得要死,就当花钱买教训吧,人家直接拿完钱就跑路了
程序员小白条:简历修改700....神奇,又不是帮你面试,咋的,简历修改从双非变92了还是没实习变成有大厂实习了
点赞 评论 收藏
分享
06-28 22:48
已编辑
广东金融学院 Java
小浪_Coding:学院本+这俩项目不是buff叠满了嘛
点赞 评论 收藏
分享
陆续:不可思议 竟然没那就话 那就我来吧 :你是我在牛客见到的最美的女孩
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务