【poj3017】Cut the Sequence

2015.03.15 21:29 Sun | 3次阅读 | 旧日oi | 固定链接 | 源码

Description
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.

题解

先吐槽一下poj。。一提交就502 bad gateway……
曾经做过两道单调队列的水题,现在发现好像还是啥也不会……最近复习一下

我的程序

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#define ll long long
using namespace std;
int n,k;
ll m,sum;
ll x[100005],dp[100005];
ll q[100005],f=1,t;
set<ll> s;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) 
    {
        scanf("%lld",&x[i]);
        if(x[i]>m) 
        {
            puts("-1");
            return 0;
        }
        sum+=x[i];
        while(sum>m) sum-=x[++k];
        while(f<=t&&x[q[t]]<=x[i]) t--;
        q[++t]=i;
        while(f<=t&&q[f]<=k) f++;
        dp[i]=0x3f3f3f3f3f3f3f3fll;
        ll kk=k;
        for(int j=f;j<=t;j++)
        {
            ll tmp=dp[kk]+x[q[j]];
            dp[i]=min(dp[i],tmp);
            kk=q[j];
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}
再来一个用平衡树优化的(为什么更慢……)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
#define ll long long
#define maxn 100005
using namespace std;
ll num[maxn],q[maxn];
ll dp[maxn];
int n,k,f,t=-1;
ll m,sum;
multiset<ll> s;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&num[i]);
        if(num[i]>m)
        {
            puts("-1");
            return 0;
        }
        sum+=num[i];
        while(sum>m) sum-=num[k++];
        while(f<=t&&num[i]>=num[q[t]])
        {
            if(f<t) s.erase(dp[q[t-1]]+num[q[t]]);
            t--;
        }
        q[++t]=i;
        if(f<t) s.insert(dp[q[t-1]]+num[q[t]]);
        while(q[f]<k)
        {
            if(f<t) s.erase(dp[q[f]]+num[q[f+1]]);
            f++;
        }
        dp[i]=dp[k-1]+num[q[f]];
        if(f<t&&dp[i]> *s.begin())
        dp[i]=*s.begin();
    }
    cout<<dp[n]<<endl;
    return 0;
}```