「美团CodeM复赛」送外卖 - 动态规划+三进制状态压缩

题目大意

    一张$n$个点$m$条有向边的图上，有$q$个配送需求，需求的描述形式为$(s_i,t_i,l_i,r_i)$,即需要从点$s_i$送到$t_i$，在时刻$l_i$之后（包括$l_i$）可以在$s_i$领取货物，需要在时刻$r_i$之前（包括$r_i$）送达$t_i$，每个任务只需完成一次。
    图上的每一条边均有边权，权值代表通过这条边消耗的时间。在时刻$0$有一个工作人员在点$1$上，求他最多能完成多少个配送任务。
    在整个过程中，可以认为领货跟交货都是不消耗时间的，时间只花费在路程上。当然在一个点逗留也是允许的。

---

题目分析

注意$q\le10$，因此我们可以对配送的状态进行压缩。
尝试用三进制表示状态：$0$还未接到外卖，$1$正在配送外卖，$2$配送外卖完成。
因此可以用$3^{10}$个状态表示所有情况。

因为时间$t\le10^6$，因此不能将时间设入状态，考虑间接设置状态。

设$f[i,j]$表示当前状态为$i$，在$j$结点的最少时间。

用floyd预处理出多源最短路，接着枚举下一个完成哪个任务进行转移即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

int n,m,Q,Triple[15],a[60005][15],f[60005][25],map[25][25];

struct Query {
	int from,to,st,ed;
} q[100005];

int main() {
	n=Get_Int();
	m=Get_Int();
	Q=Get_Int();
	Triple[0]=1;
	for(int i=1; i<=Q; i++)Triple[i]=Triple[i-1]*3;
	for(int S=0; S<Triple[Q]; S++) {
		int x=S,cnt=0;
		while(x) {
			a[S][cnt++]=x%3;
			x/=3;
		}
	}
	memset(f,0x3f,sizeof(f));
	memset(map,0x3f,sizeof(map));
	for(int i=1; i<=n; i++)map[i][i]=0;
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int(),v=Get_Int();
		map[x][y]=min(map[x][y],v);
	}
	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
	for(int i=0; i<Q; i++) {
		q[i].from=Get_Int();
		q[i].to=Get_Int();
		q[i].st=Get_Int();
		q[i].ed=Get_Int();
	}
	f[0][1]=0;
	int state=Triple[Q];
	for(int Now=0; Now<state; Now++)
		for(int j=1; j<=n; j++)
			if(f[Now][j]<0x3f3f3f3f) {
				for(int k=0; k<Q; k++)
					if(a[Now][k]==0) { //0->1
						int Next=Now+Triple[k];
						f[Next][q[k].from]=min(f[Next][q[k].from],max(f[Now][j]+map[j][q[k].from],q[k].st));
					} else if(a[Now][k]==1) { //1->2
						int Next=Now+Triple[k];
						if(f[Now][j]+map[j][q[k].to]<=q[k].ed)f[Next][q[k].to]=min(f[Next][q[k].to],f[Now][j]+map[j][q[k].to]);
					}
			}
	int ans=0;
	for(int Now=0; Now<state; Now++)
		for(int j=1; j<=n; j++)
			if(f[Now][j]<0x3f3f3f3f) {
				int cnt=0;
				for(int k=0; k<Q; k++)
					if(a[Now][k]==2)cnt++;
				ans=max(ans,cnt);
			}
	printf("%d\n",ans);
	return 0;
}