蓝桥杯国赛压轴题（插头dp）

蓝桥杯国赛压轴题是指蓝桥杯国赛中最难的题目，也是插头dp的经典题目。插头dp是动态规划的一种，主要用于解决排列组合问题，如求解最长公共子序列、最长上升子序列等。

在蓝桥杯国赛压轴题中，给定一个n*m的矩阵，矩阵中每个元素都是一个由0和1组成的串。要求选出一些行和一些列，使得选出的行和列的交集中的元素全为1，并且选出的行和列数最小。该问题可以使用插头dp来解决。

插头dp的核心思想是将问题转化为图论问题，将行和列分别看作图中的节点，若行i和列j的交集中的元素全为1，则在节点i和节点j之间连一条边。在此基础上，使用动态规划求解最小的节点覆盖数，即最小的选出的行和列数。

具体地，设f[S]表示覆盖集合S中的节点的最小行列数。则有状态转移方程：

f[S] = min(f[S-T]+|T|)，其中T是S的一个子集，且T中的节点必须能够被T中的其它节点覆盖。

最终的答案为f[{1,2,...,n},{1,2,...,m}]。该算法时间复杂度为O(3^n)。