以下是一些状压 DP 题目，为本蒟蒻在上 luogu 网课时所整理。篇一题解超多，故开新篇。

P3959 [NOIP2017 提高组] 宝藏

题意

给定无向图，边有权，生成一棵树，使其各边权 $\times$ 深度的和最小。节点数 $n\le12$ ，权 $\le5\times10^5$ ，边数 $\le10^3$ 。

点击查看题解

题解

PS：本题为 Yurchiu 的教练讲课例题，但教练的两个做法都被 hack（帖 1 和帖 2）。

参照题解 https://www.luogu.com.cn/blog/flashblog/solution-p3959，给出本题题解及代码。

根据以上题解所述，本代码时间复杂度为 $O(3^n \times n)$ 。由于自认为原题解不好理解，本题解将详细描述。

考虑到每条边的贡献跟它所在的层有关，所以如果我们能够将一层的边一起加进去，计算就会方便许多。于是想办法把这个转移过程状压一下。

第一部分：设 $dp1_{i,j}$ 为当前已选点集为 $i$ ，将要加入的点集为 $j$ 时，新加入的所有点与原有点之间最小的边权之和。

如何进行递推：设 $\operatorname{lb}(j)$ （代码中是 lowbit(j) 和 j&-j）是数 $j$ 的二进制非 $0$ 最低一位，即已选入的点集 $j$ 编号最小的那个点；设 $\operatorname{dis}(a,b)$ 为以 $a$ 和 $b$ 两点为端点的边的权。我们可以得到状态转移方程（为了美观，将 dp1 替换为 f；符号 $-$ 即集合意义上的）：

f_{i,j}=f_{i,j-\operatorname{lb}(j)}+\min\{\operatorname{dis}(\operatorname{lb}(j),k)\quad | \quad k \in i \}

这个递推时间复杂度为 $O(3^n \times n)$ 。注意枚举集合的顺序。

第二部分：设 $dp2_{d,i}$ 为生成树层数为 $d$ ，生成树点集为 $i$ 的最小答案。借助 $dp1$ ，我们可以得出以下状态转移方程（同样为了美观，将 dp2 替换为 g；此处疑似原题解有误）：

g_{d,i}=\min\{g_{d-1,i-j}+f_{i-j,j}\times d\quad |\quad j\subset i\}

这个递推时间复杂度仍为 $O(3^n \times n)$ 。

则答案为： $\min\{g_{i,S}\mid i\in [0,n-1]\}$ ，其中 $S$ 为 $n$ 个点全部入选。

代码

代码中的枚举子集、lowbit 等技巧已在篇一中的“前置知识”中提及。

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	#define mset(a,b) memset(a,b,sizeof(a))
	const int N=13,Inf=10000000;
	int n,m,ans=Inf,g[N][N],next[1<<N],lb[1<<N],S,dp1[1<<N][1<<N],dp2[N][1<<N];
	void add(int x,int y,int len){g[x][y]=min(g[x][y],len);}//加边！加边！加边！然后，用于递推。
	int lowbit(int x){ return lb[x&-x]; }//获取 lowbit 后的节点编号
	void yzmain()
	{
		int t1,t2,t3;
		scanf("%d%d",&n,&m);S=(1<<n)-1;
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)
				g[i][j]=Inf;
		for(int i=0;i<=n;i++)
			for(int j=0;j<=(1<<n);j++)
				dp2[i][j]=Inf;
		for(int i=0;i<=n-1;i++) lb[1<<i]=i+1;
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&t1,&t2,&t3);
			add(t1,t2,t3);add(t2,t1,t3);
		}
		for(int i=1;i<=S;i++)
		{
			int link=0,rest=S^i;
			for(int j=rest;j;j=j-1&rest)
				next[j]=link,link=j;//需要逆向枚举，保证已知推未知
			for(int j=link;j;j=next[j])
			{
				int len=Inf;
				for(int k=1;k<=n;k++)
					if(i&(1<<(k-1))) len=min(len,g[lowbit(j)][k]);
				dp1[i][j]=dp1[i][j^(j&-j)]+len;
			}
		}
		for(int i=1;i<=S;i<<=1) dp2[0][i]=0;//根据题意，选择起始点代价为0
		for(int d=1;d<=n-1;d++)
			for(int i=1;i<=S;i++)
				for(int j=i;j;j=j-1&i)
					dp2[d][i]=min(dp2[d][i],dp2[d-1][i^j]+dp1[i^j][j]*d);
		for(int i=0;i<=n-1;i++)
			ans=min(ans,dp2[i][S]);
		printf("%d\n",ans);				
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P2831 [NOIP2016 提高组] 愤怒的小鸟

题意

有 $n$ （ $\le 18$ ）个点，求最少的抛物线 $y=ax^2+bx$ 数，使得这 $n$ 个点都被经过。点横纵坐标 $\in(0,10)$ 且为实数。

点击查看题解

题解

数学推导

已知两点 $(x_1,y_1)$ ， $(x_2,y_2)$ ，求经过这两点的抛物线 $y=ax^2+bx$ 。

将两点代入，得：

\begin{cases} ax_1^2+bx_1=y_1 \\\ \\\ ax_2^2+bx_2=y_2 \end{cases}

在第一个等式两边各乘上 $x_2$ ，第二个等式两边各乘上 $x_1$ ，得：

\begin{cases} ax_1^2x_2+bx_1x_2=y_1x_2 \\\ \\\ ax_1x_2^2+bx_1x_2=y_2x_1 \end{cases}

我们于是发现，都有公共项 $bx_1x_2$ ，所以我们将两个等式相减，得：

y_1x_2-y_2x_1=a(x_1^2x_2-x_1x_2^2)

于是我们将 $(x_1^2x_2-x_1x_2^2)$ 除到左式，得：

a=\dfrac{y_1x_2-y_2x_1}{x_1^2x_2-x_1x_2^2}

我们求出了 $a$ 。那么我们以同样方式求出 $b$ ：

首先我们先要将 $a$ 的项消掉，第一个等式乘上 $x_2^2$ ，第二个等式两边各乘上 $x_1^2$ ：

\begin{cases} y_1x_2^2=ax_1^2x_2^2+bx_1x_2^2 \\\ \\\ y_2x_1^2=ax_1^2x_2^2+bx_1^2x_2 \end{cases}

两式相减：

y_1x_2^2-y_2x_1^2=b(x_1x_2^2-x_1^2x_2)

b=\dfrac{y_1x_2^2-y_2x_1^2}{x_1x_2^2-x_1^2x_2}

于是，我们只要知道抛物线上的两个点，我们必然能够求出抛物线方程 $y=ax^2+bx$ 中 $a$ ， $b$ 的值。

给出坐标 $(x,y)$ ，判断这个点是否在抛物线 $y=ax^2+bx$ 上。

抛物线可转化为： $ax^2+bx-y=0$ 。

所以只需判断 $ax^2+bx-y$ 是否为 $0$ 即可。

实现部分

求抛物线：

void calc(double &a,double &b,double x1,double y1,double x2,double y2)
{
	a=(x2*y1-x1*y2)/(x1*x2*(x1-x2));
	b=(x2*x2*y1-x1*x1*y2)/(x1*x2*(x2-x1));
}

首先，我们对每两个点，求出 $a$ 和 $b$ 。

若两个点的横坐标相同，无解。
若 $a$ 为正数，两个点就不能用此抛物线经过（开口向上，不符题意）。

设 $line(i,j)$ 表示经过两个点 $i$ 和 $j$ 的抛物线所经过的点集合（状态压缩）。求出 $a$ 和 $b$ 后，从 $1$ 到 $n$ 判断一遍求解。

这部分时间复杂度为 $O(n^3)$ 。

设 $f(S)$ 表示经过点的集合为 $S$ 时，最少抛物线数。

我们可以得到如下状态转移方程（不太好描述，按代码写的）：

\begin{cases} f(0)=0 & \text{经过 0 个点需抛物线数为 0} \\\ f(S \cup line(i,j))=\min\{f(S)+1,f(S \cup line(i,j))\} & \text{增加一个含点数}\ge2\text{的集合} \\\ f(S\cup i)=\min\{f(S)+1,f(S\cup i)\} & \text{增加一个点} \end{cases}

这部分时间复杂度为 $O(2^nn^2)$ 。最坏运行 $84,934,656$ 次，不过不会跑满，可以通过本题。

若要使时间复杂度达到 $O(2^nn)$ ，请参考这位大佬的题解。

注意：由于 C++ 的特性，判断两个实数是否相等，不能直接 if(a==b)，而是 if(fabs(a-b)<0.00000001)。因为 C++ 存储实数有误差。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=20;
	const double eps=0.00000001;
	int n,f[1<<N],end,line[N][N];
	struct Pos{double x,y;}p[N];
	void calc(double &a,double &b,double x1,double y1,double x2,double y2)
	{
		a=(x2*y1-x1*y2)/(x1*x2*(x1-x2));
		b=(x2*x2*y1-x1*x1*y2)/(x1*x2*(x2-x1));
	}
	void init()
	{
		memset(p,0,sizeof(p));
		memset(line,0,sizeof(line));
		memset(f,0x3f,sizeof(f));
		end=(1<<n)-1;f[0]=0;
	}
	void yzmain()
	{
		int T,tmp;
		double a,b;
		scanf("%d",&T);
		while(T--)
		{
			scanf("%d%d",&n,&tmp);init();
			for(int i=1;i<=n;i++)
				scanf("%lf%lf",&p[i].x,&p[i].y);
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
				{
					if(fabs(p[i].x-p[j].x)<eps) continue;
					calc(a,b,p[i].x,p[i].y,p[j].x,p[j].y);
					if(a>-eps) continue;
					tmp=0;tmp|=1<<(i-1);f[tmp]=1;tmp|=1<<(j-1);f[tmp]=1;
					for(int k=1;k<=n;k++)
						if(fabs(a*p[k].x*p[k].x+b*p[k].x-p[k].y)<eps)
							tmp|=1<<(k-1),f[tmp]=1;
					line[i][j]=tmp;
				}
			for(int i=0;i<=end;i++)
				for(int j=1;j<=n;j++)
				{
					if(i&(1<<(j-1))) continue;
					f[i|(1<<(j-1))]=min(f[i|(1<<(j-1))],f[i]+1);
					for(int k=1;k<=n;k++)
						f[i|line[j][k]]=min(f[i|line[j][k]],f[i]+1);
				}
			printf("%d\n",f[end]);
		}
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}