P7990题解

Suffix_Sum · 2021-12-25 13:22:47 · 个人记录

USACO银组第一题，个人觉得比第二第三都要难一些。

看到这一题，我首先想到了动规，但很明显，设二维是 n^2 复杂度，直接爆炸。

既然不能动规，那大概率就是贪心。

考虑每一个敌人的点，分成 m+1 段，每一段互相不干扰。

对于每一段，有三种选择，不放奶牛，放 1 只奶牛，和放 2 只奶牛。

不放奶牛就得不到其中的草地；只要放 1 只奶牛就可以获得放 1 只奶牛的最大值；只要放 2 只奶牛，就能把区间内所有的牧场都占下。