首页 > 代码库 > BZOJ1082 [SCOI2005]栅栏
BZOJ1082 [SCOI2005]栅栏
最近做做搜索题吧。。。^_^
然后又被虐了。。。T T
这还是一道usaco题。。。我去。。。
为了方便叙述，FJ买的叫"木块"，要被切掉的叫"木材"！！！（我也是醉了0.0）
根据贪心，我们肯定先搞到小的木块。。。于是先对要买的木块进行排序，然后二分答案
之后如何判断：
裸的dfs肯定过不掉T T，考虑优化
（1）如果两块木块长度相同，第一个已经被dfs过了且从第x块木材上被切下来，则第二个也至少要从第x块木材上切。（貌似是对称性原理的说。。。）
（2）某巨巨："用waste表示每一个已经裁过的木材浪费的木材和，所谓浪费的木材就是最小的木块都比它大，那么他当前就已经裁不出任何木块了。就把这个木材加到waste去，如果waste>木材和-s[mid]，说明这样裁木材是错误的，所以减枝。"
两个优化使得搜索速度快的飞起！！！
1 /************************************************************** 2 Problem: 1082 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:4 ms 7 Memory:820 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13 14 using namespace std;15 const int N = 1005;16 int n, m, waste, l, r, mid;17 int a[N], b[N], c[N], s[N], T;18 19 inline int read(){20 int x = 0;21 char ch = getchar();22 while (ch < ‘0‘ || ch > ‘9‘)23 ch = getchar();24 25 while (ch >= ‘0‘ && ch <= ‘9‘){26 x = x * 10 + ch - ‘0‘;27 ch = getchar();28 }29 return x;30 }31 32 bool dfs(int x, int pos){33 if (!x) return 1;34 if (s[mid] + waste > T) return 0;35 for (int i = pos; i <= m; ++i)36 if (c[i] >= b[x]){37 c[i] -= b[x];38 if (c[i] < b[1])39 waste += c[i];40 if (b[x] == b[x - 1]){41 if (dfs(x - 1, i))42 return 1;43 }44 else if (dfs(x - 1, 1)) return 1;45 if (c[i] < b[1]) waste -= c[i];46 c[i] += b[x];47 }48 return 0;49 }50 51 int main(){52 m = read();53 for (int i = 1; i <= m; ++i)54 a[i] = read(), T += a[i];55 n = read();56 for (int i = 1; i <= n; ++i)57 b[i] = read();58 sort(a + 1, a + m + 1);59 sort(b + 1, b + n + 1);60 for (int i = 1; i <= n; ++i)61 s[i] = s[i - 1] + b[i];62 while (s[n] > T) --n;63 l = 0, r = n + 1;64 while (l + 1 < r){65 waste = 0;66 memcpy(c, a, sizeof(a));67 mid = l + r >> 1;68 if (dfs(mid, 1)) l = mid;69 else r = mid;70 }71 printf("%d\n", l);72 return 0;73 }
BZOJ1082 [SCOI2005]栅栏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。