## 【poj3017】Cut the Sequence

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

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.

# 题解

## 我的程序

#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;
}
`