题目链接

题意分析

首先这道题不可以使用简单的贪心来做

根据$DP$ 我们令$dp[i]$表示当前到了$i$一共做了$dp[i]$次合并

$pre[i]$表示当前合并到了$i$后序列末尾的数

那么$$dp[i]=min{dp[j]+i-j,sum[i]-sum[j]≥pre[j]}$$

可惜是$O(n^2)$的

我们考虑由于是$dp[i]=dp[j]+val_i$的形式

所以我们可以使用单调队列优化

\[sum[i]≥sum[j]+pre[j]
\]

根据贪心法则我们希望恰好满足

所以我们维护一个递增的单调队列

CODE:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<cstdlib>

#include<string>

#include<queue>

#include<map>

#include<stack>

#include<list>

#include<set>

#include<deque>

#include<vector>

#include<ctime>

#define ll long long

#define inf 0x7fffffff

#define N 500008

#define IL inline

#define M 1008611

#define D double

#define ull unsigned long long

#define R register

using namespace std;

template<typename T>IL void read(T &_)

{

    T __=0,___=1;char ____=getchar();

    while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}

    while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}

    _=___ ? __:-__;

}

/*-------------OI使我快乐-------------*/

int n,head,tail;

int num[N],que[N],dp[N];

ll sum[N],pre[N];

int main()

{

//	freopen(".in","r",stdin);

//	freopen(".out","w",stdout);

    read(n);

    for(R int i=1;i<=n;++i) read(num[i]);

    for(R int i=1;i<=n;++i) sum[i]=sum[i-1]+1ll*num[i];

    head=0;tail=1;

    for(R int i=1;i<=n;++i)

    {

        while(head+1<tail&&sum[i]>=sum[que[head+1]]+pre[que[head+1]]) ++head;

        pre[i]=sum[i]-sum[que[head]];dp[i]=i-que[head]-1+dp[que[head]];

        while(head<tail&&sum[i]+pre[i]<sum[que[tail-1]]+pre[que[tail-1]]) --tail;

        que[tail++]=i;

    }

    printf("%d\n",dp[n]);

//	fclose(stdin);

//	fclose(stdout);

    return 0;

}

巴特西

P2300 合并神犇

题目链接

题意分析

CODE:

HEOI 2019 RP++

最新文章

热门文章