CodeForces_1400E Clear the Multiset(分治)

Clear the Multiset

time limit per test：2 seconds memory limit per test：256 megabytes

Problem Description

You have a multiset containing several integers. Initially, it contains a 1 a_1 a1​ elements equal to 1, a 2 a_2 a2​ elements equal to 2, …, a n a_n an​ elements equal to n.

You may apply two types of operations:

• choose two integers l l l and r r r ( l ≤ r l≤r l≤r), then remove one occurrence of l l l, one occurrence of l + 1 l+1 l+1, …, one occurrence of r r r from the multiset. This operation can be applied only if each number from l l l to r r r occurs at least once in the multiset;
• choose two integers i i i and x x x ( x ≥ 1 x≥1 x≥1), then remove x x x occurrences of i i i from the multiset. This operation can be applied only if the multiset contains at least x x x occurrences of i i i.

What is the minimum number of operations required to delete all elements from the multiset?

Input

The first line contains one integer n n n ( 1 ≤ n ≤ 5000 1≤n≤5000 1≤n≤5000).

The second line contains n integers a 1 a_1 a1​, a 2 a_2 a2​, …, a n a_n an​ ( 0 ≤ a i ≤ 1 0 9 0≤a_i≤10^9 0≤ai​≤109).

Output

Print one integer — the minimum number of operations required to delete all elements from the multiset.

Sample Input

4

1 4 1 1

Sample Output

2

題意

有一個多重集，其中值為 i i i的數字有 a i a_i ai​個 ( 1 ≤ i ≤ n ) (1\le i \le n) (1≤i≤n)。可以進行兩種操作：

• 選擇兩個數 l l l， r ( l ≤ r ) r(l\le r) r(l≤r)，從集合删除值為 l l l到 r r r的各删除一個。需保證 l l l到 r r r中每種值至少有一個。
• 選擇兩個數 i , x i,x i,x，從集合中删除 x x x個值為 i i i的數。需保證目前集合中值為 i i i的數至少有 x x x個。

求最少的操作次數使集合為空。

題解

隻考慮操作2，是以最多需要n次操作。

設 m i = m i n ( a 1 , a 2 , . . . , a n ) mi = min(a_1, a_2, ..., a_n) mi=min(a1​,a2​,...,an​).若要執行操作1，則一定是執行mi次 l = 1 , r = n l=1,r=n l=1,r=n(若少于mi次，則實際上還是需要n次操作2，若多于mi次，則不符合條件)。

執行mi次操作後，剩下的 a i > m i a_i > mi ai​>mi的則被分成若幹段連續區間。對于每一段區間，遞歸處理，考慮其隻需要使用操作2，或需要若幹次操作1的最小操作數使集合為空。

#include<stdio.h>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#define dbg(x) cout<<#x<<" = "<<x<<endl;
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
#define eps 1e-8
   
using namespace std;
typedef long long LL;  
typedef pair<int, int> P;
const int maxn = 5020;
const int mod = 1000000007;
int a[maxn];
int dfs(int l, int r, int up);

int main()
{
    int n, m, i, j, k;
    scanf("%d", &n);
    for(i=1;i<=n;i++)
        scanf("%d", &a[i]);
    printf("%d", dfs(1, n, 0));
    return 0;
}

int dfs(int l, int r, int up)
{
    int mi = INF, i, j, sum;
    for(i=l;i<=r;i++)
        if(a[i] < mi)mi = a[i];
    sum = mi-up, i = l;
    while(i<=r){
        if(a[i]>mi){
            j=i;
            while(a[j]>mi && j<=r)
                j++;
            sum += dfs(i, j-1, mi);
            i = j;
        }
        else i++;
    }
    return min(sum, r-l+1);
}