【算法碎碎念】dilworth定理
admin
2024-03-13 15:22:03
0次

迪沃斯定理

对于一个偏序集,最少链划分(划分出集合的个数,并且每一个集合不能再大了,这个时候,个数是最少的)等于最长反链(比如求下降子序列最少划分数,等于最长链的长度)长度。
看例题理解一下。

例题

https://www.luogu.com.cn/problem/solution/P1233

思路

由于想要求最少的,下降子序列划分,所以可以换个思路求,最长上升子序列元素的个数。
最长上升子序列元素的个数=最少划分出的下降子序列的集合个数

粒子:
求2 9 5 1 4序列的最少下降子序列集合的划分:{9,5,4}、{2,1}。总共两个集合。求2 9 5 1 4序列的最长上升序列{1,4}或者{2,9}为2个,所以就是这么一会事情。

AC代码

// VsCode C++模板 | (●'◡'●)
#include #include 
using namespace std;
typedef long long LL;
int n, a, b;
struct Object {int len, width;bool operator()(const Object &a, const Object &b) {if (a.len == b.len) {return a.width > b.width;} else {return a.len > b.len;}}
} objects[5000 + 5];
int dp[5000 + 5], ans = -1;
int main() {scanf("%d", &n);dp[0] = 1;for (int i = 0; i < n; i++) {scanf("%d %d", &a, &b);objects[i].len = a;objects[i].width = b;dp[i + 1] = 1;}sort(objects + 0, objects + n, Object());for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {if (objects[i].width > objects[j].width) {dp[i] = max(dp[i], dp[j] + 1);}}ans = max(dp[i], ans);}cout << ans;return 0;
}

OlogN的优化

上面的那个for j的循环,不是欲求找一个末尾可以使得,当前i的长度加起来最大嘛。
那我们其实可以使用一下二分做一做。
我们可以缓存一个,当前已经存在的最长上升子序列,就把所有最长的子序列(i之前的)都存起来,并且我们知道这些最长序列的末尾元素知道就好了。
然后把这些已知的最长子序列,从小到达排好,幸运的是,我们可以一边做,一边维护,“从小到大排好”。
我们设置dp[n]的含义是,在i之前,长度为n的子序列,这个序列的末尾元素是多少。(我们力求,dp[n]在最后一个最小,这样不就更好的接入了嘛)
例如
{1,2,5}
{2,3,4}
我们取第二个,也就是{2,3,4}的末尾,dp[3]=4
由于n是有序的,所以可以二分查找一下,就可以了。
代码不给出了,去洛谷看题解吧。
https://www.luogu.com.cn/problem/solution/P1233

相关内容

热门资讯

智星菠萝德州辅助神器!如何下载... 智星菠萝德州辅助神器!如何下载德普之星辅助软件”原来真的是有辅助操作1)如何下载德普之星辅助软件辅助...
WPK辅助插件!aapoker... WPK辅助插件!aapoker怎么控制牌”原来有辅助项目1、起透看视 aapoker怎么控制牌辅助软...
红龙PoKer开挂工具!德扑圈... 红龙PoKer开挂工具!德扑圈透视”确实真的是有开挂方针1、该软件可以轻松地帮助玩家将德扑圈透视辅助...
WPK透视挂攻略!扑克之星辅助... WPK透视挂攻略!扑克之星辅助”果然真的是有透视挂法子1、游戏颠覆性的策略玩法,独创攻略技巧玩法,可...
红龙PoKer开挂教程!wpk... 红龙PoKer开挂教程!wpk系统是否存在作弊行为”一贯是有开挂办法1、完成wpk系统是否存在作弊行...
AApoker透视挂脚本!红龙... AApoker透视挂脚本!红龙poker辅助器免费观看”竟然存在有透视挂演示1、AApoker透视挂...
wpk开挂插件!aapoker... wpk开挂插件!aapoker怎么选牌”本来有开挂模块1、用户打开应用后不用登录就可以直接使用,点击...
微扑克透视技巧!智星菠萝辅助”... 微扑克透视技巧!智星菠萝辅助”本来是有透视学习1、操作简单,无需智星菠萝辅助手机版透视脚本,只需要使...
wpk辅助器app!aapok... wpk辅助器app!aapoker怎么开辅助器”都是真的是有辅助器策略1、下载好aapoker怎么开...
德扑之星透视工具!wpk透视是... 德扑之星透视工具!wpk透视是真的假的”本来真的有透视妙招一、wpk透视是真的假的游戏安装教程牌型概...