[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]);
}
}
}
上一篇:BestCoder Round #65 hdu5590(水题)


下一篇:BestCoder Round #86 二,三题题解(尺取法)