Tree Burning
题目链接: https://atcoder.jp/contests/agc030/tasks/agc030_b
数据范围: 略.
题解:
开始以为是左右左右这样, 发现过不去样例.
看了样例之后, 觉得是: 看左边右边哪个比较长, 走长的那个.
发现过了第一个样例, 过不去第二个了....
看了看第二个样例, 又画了画第三个样例, 加上枫哥在给我这道题之前的提示: 你要大胆猜啊...
发现: 一定是先忘一个方向连续走几个, 然后左右横跳.
这个就对了, 用数学归纳法容易证明.
所以我们只需要开始逆时针连续走了多少个, 然后用什么前缀和啥的随便求一求就好了.
求完了之后, 把序列反转再来一次即可.
代码:
- #include <bits/stdc++.h>
- #define N 1000010
- using namespace std;
- typedef long long ll;
- char *p1, *p2, buf[100000];
- #define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )
- int rd() {
- int x = 0, f = 1;
- char c = nc();
- while (c <48) {
- if (c == '-')
- f = -1;
- c = nc();
- }
- while (c> 47) {
- x = (((x <<2) + x) << 1) + (c ^ 48), c = nc();
- }
- return x * f;
- }
- ll m;
- int n;
- ll a[N];
- ll bfr[N], ans;
- void solve() {
- bfr[0] = 0;
- for (int i = 1; i <= n; i ++ ) {
- bfr[i] = bfr[i - 1] + a[i];
- }
- for (int i = 1; i <= n; i ++ ) {
- ll mdl;
- if (i & 1) {
- int x = (i - 1)>> 1;
- mdl = ((ll)m * x - (bfr[n] - bfr[n - x])) * 2 + a[n - x] + (bfr[n - x - 1] - bfr[n - x - x - 1]) * 2;
- }
- else {
- int x = i>> 1;
- mdl = (m * (x - 1) - (bfr[n] - bfr[n - x + 1])) * 2 + ((ll)m - a[n - x + 1]) + (bfr[n - x] - bfr[n - x - x]) * 2;
- }
- ans = max(ans, mdl);
- }
- }
- int main() {
- m = rd(), n = rd();
- for (int i = 1; i <= n; i ++ ) {
- a[i] = rd();
- }
- solve();
- for (int i = 1; i <= n; i ++ ) {
- a[i] = m - a[i];
- }
- reverse(a + 1, a + n + 1);
- solve();
- cout << ans << endl ;
- return 0;
- }
[Agc030B]Tree Burning_贪心
来源: http://www.bubuko.com/infodetail-3254193.html