为什么不能贪心
查看原帖
为什么不能贪心
544475
wangjiajian楼主2024/8/17 14:59

枚举有多少个休息日,对于每个休息日,遍历一周,找到使结果最大的位置,贪心放置休息日。为什么这种贪心策略是错误的(只能过几个点)?

以下是代码

#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;
}
2024/8/17 14:59
加载中...