ZJ772

· · 个人记录

这道题很明显的DP题 为什么我最近练的都是DP题

貌似和 P1220 一样带点贪心成分

而且，貌似还是线性DP？

首先我们从数据范围看起

1\le N\times M\le10^6

我们完全可以猜测这是一个O(NM)的程序

我们设dp_i为套完第i个圈后可以得到的最优结果

容易得到动态转移方程：

dp_i=dp_{i-1}+\max\limits_{1\le j\le M,r_{c,i}>r_{b,j}}v_j

可以看到时间复杂度的确是O(NM)

代码咕咕咕