JZOJ3083. 【NOIP2012模拟11.1】塔（加強）

Description

玩完骰子遊戲之後，你已經不滿足于骰子遊戲了，你要玩更進階的遊戲。

今天你瞄準了下述的好玩的遊戲：

   首先是主角：塔。你有N座塔一列排開。每座塔各自有高度，有可能相等。

   這個遊戲就不需要地圖了。

   你每次可以選擇相鄰的兩座塔合并在一起，即這兩座塔的高度疊加後變成了同一座塔。然後原本分别與這兩座塔相鄰的塔變得與這座新的塔相鄰。

   你的目标是在使用最少的操作次數在遊戲的最後獲得一列塔，這些塔的高度從左到右形成一個不下降的數列。
           

Input

第一行一個整數N。

   第二行N個整數，從左到右描述塔的高度Ai。
           

Output

僅一個整數表示最少的操作次數。

Sample Input

5

8 2 7 3 1

Sample Output

3

Hint

對于100%的資料 1<=N,Ai<=10^6

分析

非常容易就可以想到 O(N3) 的DP，

是以在這裡就不說了。

我們将題目轉換一下

變成：

• 将一個序列分成多個連續的區間，使得每個區間的和不下降，求分的區間個數最多，

現在我們想一下 O(N2) 的DP，

設 fi 表示前i個已經完成的最小次數。

設 gi 表示前i個已經完成的最小次數的最低高度。

一個 O(N2) 的DP就出來了

fi,j=∑i−1j=0min(fi−1,j+i−j−1,∑aik=1fi−1,k)

g的轉移同理。

• 但是這樣的複雜度是不能AC的。

現在我們進行優化，

打一個單調隊列。

code(c++)

#include <cstdio>
#include <cmath>
#include <math.h>
#define N 1000003
using namespace std;
int f[N],n,t,ans,l,r,d[N];
long long s[N],g[N];
int main()
{
    scanf("%d",&n);for(int i=;i<=n;i++)scanf("%d",&t),s[i]=s[i-]+t;f[]=;g[]=s[];l=r=;d[]=;
    for(int i=;i<=n;i++){while((l<r)&&(g[d[l+]]+s[d[l+]]<=s[i]))l++;f[i]=f[d[l]]+i-d[l]-;g[i]=s[i]-s[d[l]];
    while((l<=r)&&(g[d[r]]+s[d[r]]>=g[i]+s[i]))r--;d[++r]=i;}printf("%d",f[n]);
}