洛谷普及组 P1433 吃奶酪状压DP

程序员文章站 2024-01-11 18:26:28

...

题目描述

房间里放着n块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在(0,0)点处。

输入格式

第一行一个正整数n。

接下来每行2个实数，表示第i块奶酪的坐标。

两点之间的距离公式为洛谷普及组 P1433 吃奶酪状压DP

输出格式

一个数，表示要跑的最少距离，保留2位小数。

输入输出样例

输入

输出

7.41

思路

一开始偷懒采用DFS，结果最后一个测试点怎么都会超时，于是学了状态压缩动态规划（状压DP）。

▶用状压DP解决题目得先明白位运算。针对这道题简单地讲，<<是左移运算符。假设x=2，那么x<<1相当于x的二进制10后面补一个0，变成100，十进制下是4。所以<<是十进制下乘以2的意思

▶在这道题中，我们采用二进制来表示某个点的奶酪吃过了没，1表示吃过，0表示还没吃。样例中有4块奶酪，那么一开始就是0000，4块吃完后就是1111。0000~1111包含所有奶酪食用的情况(16种)。我们知道二进制下1111=10000-1，十进制就是洛谷普及组 P1433 吃奶酪状压DP ，用<<表示就是(1<<4)-1。n块奶酪呢？那就是(1<<n)-1，用这个式子就能表示所有奶酪的状况

▶接下来需要知道&（与运算符），只有1&1时才等于1，其余情况=0；要判断某状态下第 i 块奶酪吃过没，就要判断二进制的第 i 位是否为0，用 if( ( (1<<( i−1) ) & x ) ==0)，假设当前状态是x=0011，从右往左数第1、2位是1，如果要判断第3位是否为0，可以写作 if( ( ( 1<<( 3-1) ) & x ) ==0),也就是100 & 0011，结果是0000，说明第3位是0，因为第3位上1&0=0

▶然后是状态转移方程：

l[now][r] = min(l[now][r], l[pre][r-(1<<(now-1))]+dis(pre,now));

洛谷普及组 P1433 吃奶酪状压DP

▶最后只需遍历1到n，看从哪个点开始得到的路线最短，切记加上从原点(0,0)到第一个点的距离dis(0,i)

#include<iostream>
#include<cmath>
#include<string.h>
#include<iomanip>
using namespace std;
int n;
double x[16], y[16], l[16][100000]; //l[p][r]数组是点p在某种状况r下的最短路线
double dis(int a, int b) {return sqrt( (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]) );}
void DP()
{
	for(int i = 1; i <= n; i++) l[i][1<<(i-1)] = 0; //点到自身的距离为0
	for(int r = 1; r <= (1<<n)-1; r++)       	//n个奶酪的所有状态
		for(int now = 1; now <= n; now++){ 
			if((r&(1<<(now-1)))==0) continue;   //跳过未访问的点 	
			for(int pre = 1; pre <= n; pre++)       
				if((r&(1<<(pre-1)))!=0)  //保证r状态中pre那一位是1，即上个点有走过
					l[now][r] = min(l[now][r], l[pre][r-(1<<(now-1))]+dis(pre,now));
		}
}
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];
	memset(l, 127, sizeof(l)); //初始化点在各种状况下的距离
	DP();
	double mindis = 0x3f3f3f3f; //初始化为很大的数
	for(int i = 1; i <= n; i++) 
		if(l[i][(1<<n)-1]+dis(i,0) < mindis)
			mindis = l[i][(1<<n)-1]+dis(i,0);
	cout << fixed << setprecision(2) << mindis << endl; //输出2位小数
	return 0; 
}

memset(a,127,sizeof(a))表示将a数组的全部元素设置成一个非常大的数2139062143，不是数字127。

洛谷 普及组 P1433 吃奶酪 状压DP

思路