湛蓝之海 发表于 2021-12-27 23:56:12

painting fence - 分治 - Codeforces 448c

2017-08-02 14:27:18
writer：pprp
题意：
· 每块木板宽度均为1，高度为h
· n块木板连接为宽度为n的栅栏
· 每次可以刷一横或一竖(上色)
· 最少刷多少次可以使得栅栏被全部上色
· 1 ≤ n ≤ 5000
算法分析：可以横着刷，可以竖着刷，横着刷是为了减小竖着刷的次数
采用分治，每个分治中都取横着刷和竖着刷两者的最小值
代码及说明如下：
#include <iostream>
#include <queue>

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 5010;
int n;
int a;

//在递归算法中不要用n，应该考虑的是在每个部分，而不能只是在第一个递归中的角标
int dfs(int l,int r)
{
    int MIN = INF;
    int cnt = 0;

    //找到所有木板中最短的那个
    for(int i = l ; i <= r; i++)
    {
      MIN = min(MIN, a);
    }

    //将数目加上最短板长度
    cnt += MIN;

    //所有的木板减去这个长度
    for(int i = l; i <= r; i++)
    {
      a -= MIN;
    }

    int left = l;

    //分段递归解决问题
    for(int i = l; i <= r; i++)
    {
      if(a == 0)
      {
            cnt +=dfs(left,i-1);
            left = i+1 ;
      }
    }
   
    //最后一段,需要一个判断
    if(left <= r)
      cnt += dfs(left,r);

    return min(cnt,r-l+1);
}

int main()
{   
    cin >> n;   

    for(int i = 1 ; i <= n ; i++)
    {
      cin >> a;
    }
   
    cout << dfs(1,n) << endl;


    return 0;
}
代码改变世界


https://blog.51cto.com/u_15467355/4848189
页: [1]
查看完整版本: painting fence - 分治 - Codeforces 448c