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

[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]);
        }
    } 
}