1 条题解

  • 1
    @ 2019-08-27 21:00:02

    最少多少人说假话= N - 最多多少人说真话。
    我们转化为求最多右多少人说真话。
    每一个人的ai和bi对应一个区间[ai+1,n-bi],区间的长度就是有多少人排名相同分数相同,我们定义区间P的权值为有多少人的对应区间为P。
    我们要选出一些区间,这些区间两两不相交(因为相交肯定是不合法的),然后使得选出区间的权值和最大。也即是最终最多有多少人说真话。
    后面这个可以dp解决,设dp[i]表示以i结尾最多选出的人数,i不在任意一个区间内则由dp[i-1]转移过来,若在一个区间内就枚举对应的区间P,假设为[L,i],则由dp[L-1]+val[P]更新dp[i]的答案。

  • 1

信息

ID
121298
原题来源
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
被复制
1
上传者
更新时间
2019-08-10 00:20:33.985000