枚举有多少个休息日,对于每个休息日,遍历一周,找到使结果最大的位置,贪心放置休息日。为什么这种贪心策略是错误的(只能过几个点)?
以下是代码
#include <bits/stdc++.h>
#define ll long long
#define N 5002
using namespace std;
int n, new_rest, a[N], lft[N], rht[N];
bool is_rest[N];
ll now_sum, tmp, delta, ans, asum[N];
inline void update() {
int l, r = INT_MAX;
for(int i=1; i<=n; i++) {
if(is_rest[i] == true) {
l = max(l, i);
r = min(r, i);
}
}
l -= n, r += n;
for(int i=1; i<=n; i++) {
if(is_rest[i] == false)
lft[i] = i - l;
else
l = i;
}
for(int i=n; i>=1; i--) {
if(is_rest[i] == false)
rht[i] = r - i;
else
r = i;
}
}
inline ll solve(int dis) { // 求出贡献
return (asum[dis>>1]<<1) + ((dis & 1) ? a[dis>>1|1] : 0);
}
int main() {
scanf("%d", &n);
for(int i=1; i<=n; i++) {
scanf("%d", a+i);
asum[i] = asum[i-1] + a[i];
}
is_rest[1] = true;
update();
for(int i=1; i<=n; i++) {
if(is_rest[i] == false)
now_sum = now_sum + a[min(lft[i], rht[i])];
}
ans = now_sum;
for(int i=2; i<=n; i++) { // 枚举休息日个数
delta = -LONG_LONG_MAX;
for(int j=1; j<=n; j++) { // 枚举第 i 个休息日的最佳位置
if(is_rest[j])
continue;
tmp = solve(lft[j]-1) - solve(lft[j]+rht[j]-1) + solve(rht[j]-1);
if(tmp > delta) {
new_rest = j;
delta = tmp;
}
}
is_rest[new_rest] = true;
now_sum += delta;
update();
if(now_sum > ans)
ans = now_sum;
}
printf("%lld\n", ans);
return 0;
}