loj #6177. 「美团 CodeM 初赛 Round B」送外卖2 状压dp floyd

LINK：#6177.美团送外卖2

一道比较传统的状压dp题目.

完成任务需要知道自己在哪已经完成的任务集合自己已经接到的任务集合。

考虑这个dp记录什么由于存在时间的限制考虑记录最短时间因为时间越短对于任务来说越优。

考虑设f[i][j][k]表示已经做完的任务为i接受的任务为j上次做的任务为k.

虽然看起来状态数为\(2^q\cdot 2^q\cdot q\)但是考虑j枚举的只是i的补集的子集所以这样做状态数为\(3^q\cdot q\)

复杂度需要多乘一个q枚举决策 \(3^q\cdot q^2\)

看起来能过的样子但是空间爆了原因是空间复杂度是上述的分析.

考虑hash发现很难hash的不重复这个时候考虑三进制状压因为一个任务有三种状态所以三进制状压是一种很好的hash.

这样优化过空间之后就能过了.

const int MAXN=11,maxn=21;

int n,m,Q,ans;

int a[maxn][maxn],v[60010];

int f[60010][MAXN],bas[maxn];

struct wy{int s,t,l,r;}t[maxn];

int main()

{

	//freopen("1.in","r",stdin);

	get(n);get(m);get(Q);

	memset(a,0x3f,sizeof(a));

	memset(f,0x3f,sizeof(f));

	rep(1,m,i)

	{

		int x,y,z;

		get(x);get(y);get(z);

		a[x][y]=min(a[x][y],z);

	}

	bas[0]=1;

	rep(1,n,i)a[i][i]=0;

	rep(1,n,k)rep(1,n,i)rep(1,n,j)a[i][j]=min(a[i][j],a[i][k]+a[k][j]);

	rep(1,Q,i)

	{

		int get(s1);int get(s2);

		int get(s3);int get(s4);

		t[i]=(wy){s1,s2,s3,s4};

		bas[i]=bas[i-1]*3;

	}

	rep(1,Q,i)f[bas[i-1]][i]=max(a[1][t[i].s],t[i].l);

	rep(1,bas[Q]-1,i)

	{

		v[i]=v[i/3]+(i%3==2);

		rep(1,Q,j)

		{

			if(f[i][j]>INF)continue;

			int st;ans=max(ans,v[i]);

			if(i/bas[j-1]%3==1)st=t[j].s;

			else st=t[j].t;

			rep(1,Q,k)

			{

				if(i/bas[k-1]%3==0)

				{

					int ss=i+bas[k-1];

					if(f[i][j]+a[st][t[k].s]<=t[k].r)f[ss][k]=min(f[ss][k],max(f[i][j]+a[st][t[k].s],t[k].l));

				}

				if(i/bas[k-1]%3==1)

				{

					int ss=i+bas[k-1];

					if(f[i][j]+a[st][t[k].t]<=t[k].r)f[ss][k]=min(f[ss][k],f[i][j]+a[st][t[k].t]);

				}

			}

		}

		//puts("");

	}

	put(ans);

	return 0;

}

巴特西

loj #6177. 「美团 CodeM 初赛 Round B」送外卖2 状压dp floyd

最新文章

热门文章