解题报告：luogu P1433 吃奶酪

题目链接：P1433 吃奶酪

我感觉可以改成：【模板】TSP问题(商旅问题) 了。

爆搜\(T\)一个点，考虑状压\(dp\)（还是爆搜）。

我们用\(dp[i][j]\)表示现在是\(i\)状态，站在了\(j\)点。

那什么是状态呢？我们用一个\(01\)串表示每一点有无被走过（\(0\)是没走过，\(1\)是已走过），那么转移方程就是：

\[dp[i][j]=min(dp[i][j],dp[i\&((1<<n)-1-(1<<(j-1)))][k]+dis[j][k])
\]

好好理解下，就是吃掉走过的每一点。

复杂度就是\(O(2^nn^2)\)，对于\(n\leqslant15\)的数据，上界为\(7372800\),可以通过本题，还跑得挺快。

\(Code\):

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

struct node

{

	double x,y;

}a[17];

int n;

double dp[65005][17];

double minn=21247483647;

double dis(node m,node n){return sqrt((m.x-n.x)*(m.x-n.x)+(m.y-n.y)*(m.y-n.y));}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=(1<<15);i++)

	{

		for(int j=1;j<=15;j++) dp[i][j]=214748364;

	}

	for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);

	for(int i=1;i<=n;i++) dp[1<<(i-1)][i]=0;//从零开始扫会RE

	for(int i=1;i<=(1<<n)-1;i++)

	{

		for(int j=1;j<=n;j++)

		{

			if(!(1<<(j-1)&i)) continue;

			for(int k=1;k<=n;k++)

			{

				if(j==k) continue;

				if(!(1<<(k-1)&i)) continue;

				dp[i][j]=min(dp[i][j],dp[i&((1<<n)-1-(1<<(j-1)))][k]+dis(a[j],a[k]));

			}

		}

	}

	node e;

	e.x=e.y=0;

	for(int i=1;i<=n;i++) minn=min(minn,dp[(1<<n)-1][i]+dis(a[i],e));

    //注意这里把原点算上

	printf("%.2lf\n",minn);

	return 0;

}

转移方程有简单点的写法：

\[dp[i][j]=min(dp[i][j],dp[i-(1<<(j-1))][k]+dis[j][k])
\]

被骗了吧......

巴特西

解题报告：luogu P1433 吃奶酪

\(Code\):

最新文章

热门文章