首页 > 代码库 > BZOJ1863 [Zjoi2006]trouble 皇帝的烦恼
BZOJ1863 [Zjoi2006]trouble 皇帝的烦恼
貌似以前做到过这题。。。结果没搞出来T T
现在终于会了！谁想出来的，这么巧妙>.<
首先二分总的勋章数，然后判断可行性。
判断方法（dp）：
令a[i]表示i与1最少有多少相同勋章，b[i]表示i与1最多有多少相同勋章。
转移方程请自行脑补 or 见程序
最后判断a[n] == 0即可
1 /************************************************************** 2 Problem: 1863 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:44 ms 7 Memory:1976 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 13 using namespace std;14 const int N = 100005;15 int n, ans;16 int v[N], a[N], b[N];17 18 inline int read(){19 int x = 0;20 char ch = getchar();21 while (ch < ‘0‘ || ch > ‘9‘)22 ch = getchar();23 while (ch >= ‘0‘ && ch <= ‘9‘){24 x = x * 10 + ch - ‘0‘;25 ch = getchar();26 }27 return x;28 }29 30 bool check(const int x){31 int i;32 a[1] = b[1] = v[1];33 for (i = 2; i <= n; ++i){34 a[i] = max(0, v[1] + v[i] + v[i - 1] - b[i - 1] - x);35 b[i] = min(v[i], v[1] - a[i - 1]);36 }37 return !a[n];38 }39 40 int main(){41 int i, l, r, mid;42 n = read();43 for (i = 1; i <= n; ++i)44 ans = max((v[i] = read()) + v[i - 1], ans);45 l = ans - 1, r = ans * 2;46 while (l + 1 < r){47 mid = l + r >> 1;48 if (check(mid)) r = mid;49 else l = mid;50 }51 printf("%d\n", r);52 return 0;53 }
BZOJ1863 [Zjoi2006]trouble 皇帝的烦恼
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。