Lightoj1018 【状压DP】

时间:2023-03-09 13:29:00
Lightoj1018 【状压DP】

题意:

给你一个坐标系,坐标系上有N个点,然后让你用最少的线,把这些点全部连起来;

思路:

(1+15)*15/2=90条线;

然后线上有哪些点就可以知道;

然后按照线上点的个数排序,然后删掉这个线,看一下是否满足;

但是这种想法不就是每次拿点最多的线,然后判断是否满足,这样的话很明显就不行= =

所以DP。



N<=15很明显可以状压,所以想到状压DP。

每个状态表示有几个点还没有选,然后如果点数<=2,那么答案  dp[now_status]=dp[pre_status]+1;

点用二进制数表示状态,那么我们用线存的也是一个值,表示该线上有多少个点就好了(这个才是状压DP的精髓吧,一旦结果是状压,那么条件也是状压)

用line[i][j] 表示i , j上有多少个点,line[i][j] | = (1<<id);

每次状态dp[now_status]=dp[now_status&(~line[i][j])](意思就是在之前那个没有把这条线加了的点的情况转移过来)+1(加这条线以后,线多一条);

感觉也是记忆化搜索写的方便;