hdoj 5807 Keep In Touch_n^6 dp-CSDN博客

本文链接：https://blog.csdn.net/acblacktea/article/details/52156764

本文介绍了一种树形DP的优化方法，通过调整状态定义，将三个人分步到达目标节点的问题转化为更高效的求解过程。该方法避免了n^6的时间复杂度，通过具体的代码实现展示了如何利用动态规划解决此类问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

树形dp会超时 n^6
抽象出三个人是分步到达一点而不是一起到达
dp[i][j][k][0] 代表这个时间段人分别在i,j,k
dp[i][j][k][1] 代表现在这个时间只有k先到达，i，j还在上个时间段的位置
dp[i][j][k][2] 代表现在这个时间只有j,k到达，i还在上一位置
所以就形成了当第一个人到达i，第二个人到达j，第三个人到达k时,是k先到达,j后到达，最后i到达
所以这么想就好做了

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#define mod 998244353
int dp[55][55][55][4],link[55][55],n,m,lim,va[55],q;
bool ok(int a,int b,int c)
{
     if(abs(a-b)>lim||abs(b-c)>lim||abs(a-c)>lim)return 0;
     return 1;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {

        scanf("%d%d%d%d",&n,&m,&lim,&q);
        memset(link,0,sizeof(link));
        for(int i=1;i<=n;i++)scanf("%d",&va[i]);

        while(m--)
        {
           int a,b;
           scanf("%d%d",&a,&b);
           link[b][a] = 1;
        }

        for(int i=n;i>=1;i--)
            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] = dp[i][j][k][2] = 0;
                    for(int e=i+1;e<=n;e++)if(link[e][i])
                    {
                        dp[i][j][k][0] += dp[e][j][k][2];
                        dp[i][j][k][0] %= mod;
                    }
                    for(int e=j+1;e<=n;e++)if(link[e][j])
                    {
                        dp[i][j][k][2] += dp[i][e][k][1];
                        dp[i][j][k][2] %= mod;
                    }
                    for(int e=k+1;e<=n;e++)if(link[e][k])
                    {
                        dp[i][j][k][1] += dp[i][j][e][0];
                        dp[i][j][k][1] %= mod;
                    }
                    if(!ok(va[i],va[j],va[k]))dp[i][j][k][0] = 0;
                }
        while(q--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            printf("%d\n",dp[a][b][c][0]);
        }
    }
    return 0;
}