POJ 2433 – Landscaping [贪心]

Link

传送门

Mean

有N列星星,组成了若干座山峰,每次去掉一些星星从而去掉一座山峰。最后只剩下K坐山峰,问你最少去多少星星。

Analysis

每次查找最小的山峰(去掉星星数量最少)去掉即可。遍历需要姿势和技巧。

Code

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1024, inf = 0x3f3f3f3f;
int N, K, v[maxn];

int main() {
    scanf("%d%d", &N, &K);
    for(int i = 1; i <= N; ++i)
        scanf("%d", v + i);
    int ans = 0;
    while(true) {
        int best = inf, ansL, ansR, cnt = 0;
        for(int i = 1; i <= N; ++i) {
            if(v[i] <= v[i+1]) continue;
            int L = i, R = i;
            while(L >= 1 && v[L-1] <= v[L]) --L;
            while(R <= N && v[R+1] <= v[R]) ++R;
            if(L >= 1 || R <= N) {
                int t = max(v[L], v[R]), sum = 0;
                for(int j = L; j <= R; ++j)
                    sum += max(0, v[j] - t);
                if(sum < best) {
                    best = sum;
                    ansL = L, ansR = R;
                }
                ++cnt;
                i = R;
            }
        }
        if(cnt <= K) break;
        ans += best;
        int t = max(v[ansL], v[ansR]);
        for(int i = ansL; i <= ansR; ++i)
            if(v[i] > t) v[i] = t;
    }
    printf("%d\n", ans);
    return 0;
}

欢迎留言