codeforces 448CPainting Fence

心已赠人 2022-08-27 15:51 103阅读 0赞

题目：[codeforces 448CPainting Fence][]

题意：n个1\* a \[ i \] 的木板，把他们立起来，变成每个木板宽为1长为 a \[ i \] 的栅栏，现在要给栅栏刷漆，刷子宽1，每一刷子可以刷任意长，现在让你求最少需要多少刷子？

分析：题目看似没有头绪，仔细分析的话其实很简单

首先，我们假如每次都刷一个木板，即一竖行，那么需要n次刷完，可见这是一个ans的最大值。就是最差的情况下我这样刷最多为n刷。

其次：如果我们选择一横行的刷，而n个木板中最短的为min，那么我们可以花min刷，把他们都刷成a \[ i \] - min的高度，那么剩下来的栅栏又变成了开始的情况，我们可以在选择前面不为0的x个，继续按上面的方法刷，可见是一个递归调用即可。

要特别注意的是前面的条件，就是刷x个木板，最多用x刷，如果某一次求得大于x，那么取x，这样就很easy了。

其实可以归结为：其实最初的思想可以归结为优先横刷，其次竖刷（如果竖刷花费更小），注意一定要仔细。

代码：

#include <cstdio>
    #include <iostream>
    #include <string>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    const int N = 5500;
    int a[N];
    int tmp=0,ans=0;
    void solve(int s,int t)
    {
        int ma=-1,mi=0x3f3f3f3f;
        for(int i=s;i<t;i++)
        {
            if(a[i]>ma)
                ma=a[i];
            if(a[i]<mi)
                mi=a[i];
        }
        if(ma==mi){
            tmp+=min(mi,t-s);
            return ;
        }
        for(int i=s;i<t;i++)
            a[i]-=mi;
        mi=min(mi,t-s);
        tmp+=mi;
        for(int i=s;i<t;i++)
        {
            if(a[i]>0)
            {
                for(int j=i;j<t;j++)  ///枚举连续不为0段
                {
                    if(a[j]==0 || j==(t-1) &&a[j]>0)
                    {
                        if(j==(t-1) && a[j]>0)
                            j++;
                        int kk=tmp;
                        solve(i,j);
                        if(tmp-kk>(j-i)){   //判断如果求得的值比直接一行一行刷更大的话，取更小的
                            tmp=kk+(j-i);
                        }
                        i=j;break;
                    }
                }
            }
        }
    }
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=0;i<n;i++)
                scanf("%d",&a[i]);
            tmp=0;
            ans=0;
            solve(0,n);
            printf("%d\n",min(n,tmp));
        }
        return 0;
    }

[codeforces 448CPainting Fence]: http://codeforces.com/problemset/problem/448/C