首页 > 代码库 > codeforces 448C 搜索
codeforces 448C 搜索
题意：给你n条1个宽度ai长度的木条，有一个刷子可以一次刷宽度为1长度无限，问你用最少的次数把所有木条都刷满。
思路：我们可以用分治的思想来做，首先找到n条木条最短的木条i，然后减去它的值，再查找，1到i-1，和i+1到n的最小值，由于可以竖着刷，因此要比较
刷完这段区间的横着刷和竖着刷的最小值。最终即为答案。
#include <stdio.h>#include<string.h>const int maxn = 5009;const int inf = 1<<29;inline int min(int a,int b){return a < b ? a : b;}int a[maxn];int DFS(int l,int r){ int i,mina = inf; int sum = 0; for(i = l;i <= r; i++) mina = min(mina,a[i]); for(i = l;i <= r; i++) a[i] -= mina; sum = mina; int ll = l; for(i = l;i <= r; i++) { if(a[i] == 0) { sum += DFS(ll,i-1); ll = i+1; } } if(ll <= r) sum += DFS(ll,r); return min(sum,r-l+1);}int main(){ int n,i; while(~scanf("%d",&n)) { for(i=0;i<n;i++) scanf("%d",&a[i]); printf("%d\n",DFS(0,n-1)); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。