本文主要是介绍Codeforces Round #256 (Div. 2/C)/Codeforces448C_Painting Fence(分治),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
解题报告
给篱笆上色,要求步骤最少,篱笆怎么上色应该懂吧,,,刷子可以在横着和竖着刷,不能跳着刷,,,
如果是竖着刷,应当是篱笆的条数,横着刷的话,就是刷完最短木板的长度,再接着考虑没有刷的木板,,,
递归调用,,,
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 999999999999999
using namespace std;
long long n,num[5010],tt;
void dfs(long long s,long long t)
{long long ma=0,mi=inf;int i,j;for(i=s; i<=t; i++){if(ma<num[i])ma=num[i];if(mi>num[i])mi=num[i];}if(mi==ma){tt+=min(mi,t-s+1);return ;}for(i=s; i<=t; i++)num[i]-=mi;tt+=min(mi,t-s);for(i=s; i<=t; i++){if(num[i]>0){for(j=i; j<=t; j++){if(num[j]==0||(j==t&&num[j]>0)){long long kk=tt;if(j==t&&num[j]>0){dfs(i,j);if(tt-kk>(j-i+1))tt=kk+(j-i+1);}else{dfs(i,j-1);if(tt-kk>(j-i))tt=kk+(j-i);}i=j;break;}}}}
}
int main()
{int i,j;scanf("%lld",&n);for(i=1; i<=n; i++)scanf("%lld",&num[i]);dfs(1,n);printf("%lld\n",min(tt,n));return 0;
}
这篇关于Codeforces Round #256 (Div. 2/C)/Codeforces448C_Painting Fence(分治)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!