[HDU5807] [BestCoder Round #86 1004] Keep In Touch (DP)

题面

有三个人从一张N个点无重边的有向无环图上的三个点出发，每单位时间，他们分别选择当前点的一条出边走下去。有向无环图点有点权，任意时刻他们所在的三个点两两点权相差不超过K。他们可以在任意三个点同时结束。求合法的路径总数。N≤50。

分析

暴力的做法，设\(dp[i][j][k]\)表示第一个人在i,第二个人在j，第三个人在k的方案数，然后枚举三个人接着到的地方x,y,z，倒推\(dp[i][j][k]=\sum dp[x][y][z]\)。这样的时间复杂度是\(O(n^6)\)

注意到我们没必要每次让三个人一起走，只要分三次走就可以了。给dp再加一维，\(dp[i][j][k][0/1/2]\)分别表示轮到第1个人走（初始状态），第2个人走，第3个人走。然后由2转移到0，0转移到1，1转移到2即可。这样的时间复杂度是\(O(n^4)\)

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 50

#define mod 998244353

using namespace std;

int t,n,lim,m,q;

int w[maxn+5];

int g[maxn+5][maxn+5];

int dp[maxn+5][maxn+5][maxn+5][3];

void ini(){

	memset(g,0,sizeof(g));

	memset(dp,0,sizeof(dp));

}

int main(){

	int u,v,a,b,c;

	scanf("%d",&t);

	for(int cas=1;cas<=t;cas++){

		ini();

		scanf("%d %d %d %d",&n,&m,&lim,&q);

		for(int i=1;i<=n;i++) scanf("%d",&w[i]);

		for(int i=1;i<=m;i++){

			scanf("%d %d",&u,&v);

			g[u][v]=1;

		}

		for(int i=n;i>=1;i--){//题目要求u<v,所以倒推

			for(int j=n;j>=1;j--){

				for(int k=n;k>=1;k--){

					dp[i][j][k][0]=1;

					dp[i][j][k][1]=0;

					dp[i][j][k][2]=0;

					for(int u=i+1;u<=n;u++){

						if(g[i][u]){

							dp[i][j][k][0]+=dp[u][j][k][2];

							dp[i][j][k][0]%=mod;

						}

					}

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

						if(g[j][u]){

							dp[i][j][k][1]+=dp[i][u][k][0];

							dp[i][j][k][1]%=mod;

						}

					}

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

						if(g[k][u]){

							dp[i][j][k][2]+=dp[i][j][u][1];

							dp[i][j][k][2]%=mod;

						}

					}

					if(max(max(abs(w[i]-w[j]),abs(w[i]-w[k])),abs(w[j]-w[k]))>lim) dp[i][j][k][0]=0;

				}

			}

		}

		for(int i=1;i<=q;i++){

			scanf("%d %d %d",&a,&b,&c);

			printf("%d\n",dp[a][b][c][0]);

		}

	}

}