题解 P1792 【[国家集训队]种树】
皎月半洒花
2020-03-28 19:50:52
这里给出一种(虽然很简单但是没人写题解的)wqs二分的方法。
首先由于 $m$ 的限制，加上权值会有负数所以多选和少选都有可能导致结果不优，所以很容易想到要去wqs二分。二分之后就变成了求解没有 $m$ 的限制的最大值问题。自然的想法是考虑 $f_i$ 表示前 $i$ 个坑种树的最大收益，那么转移就是考虑第 $i$ 个坑种不种，即 $f_i=\max\{f_{i-1},f_{i-2}+val_i\} $ 。
但是这个地方存在一个问题，就是第 $n$ 个和第 $1$ 个之间可能存在不合法。于是就理所应当地再记一维 $0/1$ 表示第 $1$ 个坑到底种不种树，转移到 $n$ 的时候特判一下。 这样就可以解决了。
有关边界的问题可以去看我的CF958E2的题解，这里就不再赘述了。
```cpp
ll res ;
int m, n ;
int df[N] ;
ll f[N][2] ;
int base[N] ;
int cnt[N][2] ;
bool check(int x){
f[1][0] = 0 ; cnt[1][0] = 0 ;
f[1][1] = base[1] + x, cnt[1][1] = 1 ;
for (int i = 2 ; i < n ; ++ i){
if (f[i - 1][0] > f[i - 2][0] + x + base[i])
f[i][0] = f[i - 1][0], cnt[i][0] = cnt[i - 1][0] ;
else if (f[i - 1][0] < f[i - 2][0] + x + base[i])
f[i][0] = f[i - 2][0] + x + base[i], cnt[i][0] = cnt[i - 2][0] + 1 ;
else
f[i][0] = f[i - 1][0], cnt[i][0] = max(cnt[i - 1][0], cnt[i - 2][0] + 1) ;
if (f[i - 1][1] > f[i - 2][1] + x + base[i])
f[i][1] = f[i - 1][1], cnt[i][1] = cnt[i - 1][1] ;
else if (f[i - 1][1] < f[i - 2][1] + x + base[i])
f[i][1] = f[i - 2][1] + x + base[i], cnt[i][1] = cnt[i - 2][1] + 1 ;
else
f[i][1] = f[i - 1][1], cnt[i][1] = max(cnt[i - 1][1], cnt[i - 2][1] + 1) ;
}
f[n][1] = f[n - 1][1] ;
cnt[n][1] = cnt[n - 1][1] ;
if (f[n - 1][0] > f[n - 2][0] + x + base[n])
f[n][0] = f[n - 1][0], cnt[n][0] = cnt[n - 1][0] ;
else if (f[n - 1][0] < f[n - 2][0] + x + base[n])
f[n][0] = f[n - 2][0] + x + base[n], cnt[n][0] = cnt[n - 2][0] + 1 ;
else
f[n][0] = f[n - 1][0], cnt[n][0] = max(cnt[n - 1][0], cnt[n - 2][0] + 1) ;
if (f[n][0] > f[n][1]){
res = f[n][0] - (ll)x * m ;
return (bool)(cnt[n][0] >= m) ;
}
else{
res = f[n][1] - (ll)x * m ;
return (bool)(cnt[n][1] >= m) ;
}
}
int main(){
cin >> n >> m ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]) ;
if (m > n / 2) return puts("Error!"), 0 ;
int l = -2e9, r = 2e9, mid, ans ;
while (l <= r){
mid = (l + r) >> 1 ;
// cout << l << " " << r << endl ;
if (check(mid)) ans = mid, r = mid - 1 ;
else l = mid + 1 ;
}
check(ans) ; cout << res << endl ; return 0 ;
}
```