Problem 1567 - D - Sloth's Angry （ 遞歸+貪心）

Problem 1567 - D - Sloth's Angry （ 遞歸+貪心）

Problem 1567 - D - Sloth's Angry
Time Limit: 1000MS Memory Limit: 65536KB
Total Submit: 326 Accepted: 113 Special Judge: No
Description
A forest is full of sloths, they are so eager for tree leaves and as a result, very angry.
We assume that the forest is a map of N * M grids, and each of the gird is an empty land or contains a big sloth. It’s guaranteed that the sequence of the sloth is a continuous segment from the leftmost column for every row. ( You may consider that the number of columns M is infinite ).
As a sloth lover, you want to feed all the sloths as quick as possible. Every second you may select a rectangle area of the grids which only contains sloths and feed all the sloths there.
What’s the minimum time required to meet all the sloths’ needs in the forest?
Input
First line of each case contains one numbers N.(1≤??n?≤?1?000).

The following line contains N numbers Ai, each describing the length of continuous sloths sequence from the left most column in every row. ( 1 <= Ai <= 10^9 )
Output
Output the answer on a single line for each case.
Sample Input
4
3 4 5 5
Sample Output
3
Hint

The distributing situation of the sloths in the sample is as follow:

SSS

SSSS

SSSSS

SSSSS

And you can choose three rectangles to cover it.
Source

這道題有點離散化的思想的味道，比如3 4需要2次，100 ,101當然也是兩次，所以不必糾結每次操作後怎麼改變原來的值，就保持原來的值不變即可，

比如 3 4 2 5 想把每個都減去2 那麼為1 2 0 3 但是事實是和 3 4 0 5 是一樣的，更進一步還是3 4 【2】 5 ，連2 都不用變，直接無視掉 ，那麼遞歸算法就很好寫了

solve(L,R) 表示區間 [ L ,R ]全部被矩形覆蓋需要的次數

 

#include
using namespace std;
templateinline T read(T&x)
{
    char c;
    while((c=getchar())<=32)if(c==EOF)return 0;
    bool ok=false;
    if(c=='-')ok=true,c=getchar();
    for(x=0; c>32; c=getchar())
        x=x*10+c-'0';
    if(ok)x=-x;
    return 1;
}
template inline T read_(T&x,T&y)
{
    return read(x)&&read(y);
}
template inline T read__(T&x,T&y,T&z)
{
    return read(x)&&read(y)&&read(z);
}
template inline void write(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
templateinline void writeln(T x)
{
    write(x);
    putchar('\n');
}
//-------ZCC IO template------
const int maxn=1e6+10;
const double inf=999999999;
#define lson (rt<<1),L,M
#define rson (rt<<1|1),M+1,R
#define M ((L+R)>>1)
#define For(i,t,n) for(int i=(t);i<(n);i++)
typedef long long  LL;
typedef double DB;
typedef pair P;
#define bug printf("---\n");
#define mod  100000000
LL a[maxn];
int n;
LL solve(int l,int r)
{
    LL len=LL(r-l+1),sum=1,pos=l;
    LL minv=a[l];
    for(int i=l;i<=r;i++)
        minv=min(minv,a[i]);///貪心在於每次找到右端的最小值，相鄰連續的一起減去
    for(int i=l;i<=r;i++)
    {
        if(a[i]==minv)
        {
            sum+=solve(pos,i-1);//把i的位置“變為 0 ”，計算這個之前的次數
            pos=i+1;//更新pos的位置
        }
    }
    if(pos<=r)//最後剩下的區間
        sum+=solve(pos,r);
    return min(len,sum);//最小值
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(read(n))
    {
        for(int i=1;i<=n;i++)
            read(a[i]);
        writeln(solve(1,n));
    }
    return 0;
}

/*
4
3 4 5 5
4
3 4 2 5
6
3 4 1 3 4 1
*/