无情悟空

文章
7
资源
0
加入时间
3年2月4天

LOJ2540 「PKUWC2018」随机算法(状态压缩)

传送门:https://loj.ac/problem/2540solutionsolutionsolution:直接状压dpdpdp做fs,if_{s,i}fs,i​表示独立集的状态为sss,考虑到排列的第iii位枚举下一位转移考虑下一位可以填什么考虑现在可以加入独立集的点,之前肯定没考虑过,直接转移到fs∪x,i+1f_{s∪{x},i+1}fs∪x,i+1​不可以加入独立集的点...