正文

hdu_5807_Keep In Touch(分段dp)

IP云
IP云V管理员/3 阅读
09/29
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：hdu_5807_Keep In Touch

题意：

在Byteland一共有nn个城市，编号依次为11到nn，同时有mm条单向道路连接着这些城市，其中第ii条道路的起点为u_iu​i​​，终点为v_i(1\leq u_i < v_i\leq n)v​i​​(1≤u​i​​<v​i​​≤n)。特工团队一共有33名成员：007，008，以及009，他们将要执行qq次秘密任务。在每次任务中，三人可能会处于三个不同的城市，他们互相之间通过对讲机保持联络。编号为ii的城市的无线电频为w_iw​i​​，如果两个城市的无线电频差值的绝对值不超过KK，那么无线电就可以接通。三个特工每个时刻必须要选择一条道路，走到下一个城市，每条道路都只需要花费11单位时间。他们可以选择在任意城市终止任务，甚至可以在起点就终止任务，但不允许在道路上终止任务。现在他们想知道，对于每次任务，给定三个人的起始位置，有多少种可能的合法行动方案，使得行动过程中任意在城市的时刻，他们都可以两两联络？两个方案被视作不同当且仅当至少存在一个人在某一时刻所在的城市不同。注意：33个特工必须同时结束任务。
题解：

1004 Keep In Touch

考虑dp，设f[i][j][k]表示三个人分别在i,j,k时的方案数，直接转移是O(n^6)的。

于是考虑加维，设f[i][j][k][now]表示三个人分别在i,j,k,时，目前准备走now这个人的方案数，那么转移复杂度就降低到了O(n^4)。

这题的套路就是分段DP，朴素的同时转移会枚举三个点，所以会达到O(n6)，

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=+,mod=; int t,n,m,K,q,x,y,z,w[N],g[N][N],dp[N][N][N][]; int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&n,&m,&K,&q);
F(i,,n)scanf("%d",w+i);
memset(g,,sizeof(g)),memset(dp,,sizeof(dp));
F(i,,m)scanf("%d%d",&x,&y),g[x][y]=;
for(int i=n;i>=;i--)
for(int j=n;j>=;j--)
for(int k=n;k>=;k--)
{
if(abs(w[i]-w[j])<=K&&abs(w[i]-w[k])<=K&&abs(w[k]-w[j])<=K)
(dp[i][j][k][]+=)%=mod;
else dp[i][j][k][]=;
if(dp[i][j][k][])F(ii,,i-)if(g[ii][i])
(dp[ii][j][k][]+=dp[i][j][k][])%=mod;
if(dp[i][j][k][])F(ii,,j-)if(g[ii][j])
(dp[i][ii][k][]+=dp[i][j][k][])%=mod;
if(dp[i][j][k][])F(ii,,k-)if(g[ii][k])
(dp[i][j][ii][]+=dp[i][j][k][])%=mod;
}
while(q--)scanf("%d%d%d",&x,&y,&z),printf("%d\n",dp[x][y][z][]);
}
return ;
}