HDU5807分段dp

DAG图。

【题意】
n(50)个城市m(c(n,2))条单向边(x,y)，保证x<y
对于三个点(x,y,z)如果abs(w[x]-w[y])<=K && abs(w[x]-w[y])<=K && abs(w[x]-w[y])<=K则这是一个合法状态。
问你，如果我们从(x,y,z)出发，可以在合法状态中任意行走任意终止，有多少种不同的行走路径数

f[i][j][k] = ∑f[ii][jj][kk]，ii，jj，kk分别为i，j，k的直接后继

时间复杂度是O(n^6)的，需要优化。

另开一维枚举当前要走的人。

我们假定先走k，再走j，最后走i，目前在i，j，k。

f[i][j][k][0]表示k，j，i走完下一轮继续走k，j，i的方案数f[u][j][k][2] += f[i][j][k][0]；

f[i][j][k][1]表示k走完下一步走j，再走i的方案数f[i][u][k][1] += f[i][j][k][2]；

f[i][j][k][2]表示k，j走完下一步走i的方案数f[i][j][u][0] += f[i][j][k][1]；

倒着dp

具体转移是这样子的——
if (!ok(i, j) || !ok(i, k) || !ok(j, k))f[i][j][k][0] = 0;
else gadd(f[i][j][k][0], 1);
//这个DP的起点条件并不一定是要满足ok(i,j)&&ok(i,k)&&ok(j,k)，因为这个状态可能是中途状态
if (f[i][j][k][0])
for (int u = 1; u < i; ++u)if (e[u][i])
gadd(f[u][j][k][2], f[i][j][k][0]);
if(f[i][j][k][2])
for (int u = 1; u < j; ++u)if (e[u][j])
gadd(f[i][u][k][1], f[i][j][k][2]);
if(f[i][j][k][1])
for (int u = 1; u < k; ++u)if (e[u][k])
gadd(f[i][j][u][0], f[i][j][k][1]);

【题意】
n(50)个城市m(c(n,2))条单向边(x,y)，保证x<y
对于三个点(x,y,z)如果abs(w[x]-w[y])<=K && abs(w[x]-w[y])<=K && abs(w[x]-w[y])<=K则这是一个合法状态。
问你，如果我们从(x,y,z)出发，可以在合法状态中任意行走任意终止，有多少种不同的行走路径数
【类型】
分段式DP 打破题目约束
【分析】
这道题可以AC的复杂度最多只能为O(n^4)
而一个状态是O(n^3)，如果我们暴力枚举两个状态，并做转移，复杂度是O(n^6)的。
于是我们要尝试优化——
我们发现，我们在转移的时候，可以考虑的不再是三重循环转移，而是分步式转移。
即，虽然题目要求是三个人同时走，但是我们可以把其转化为三个人轮流走的情况。
因为同时走的复杂度是是要做三种枚举。所以我们定义状态的一二三步
即f[i][j][k][0]表示，下一步是i走
即f[i][j][k][1]表示，下一步是j走
即f[i][j][k][2]表示，下一步是k走
这样答案的输出是f[i][j][k][0]，这时三个人步长相同。
因为我们计算的时候，按照基本转移方程，f[i][j][k]+=f[ii][jj][kk]，(ii,jj,kk)是(i,j,k)的合法后继
所以，(i,j,k)较大的要先算出来。于是我们倒着展开DP。
具体转移是这样子的——
if (!ok(i, j) || !ok(i, k) || !ok(j, k))f[i][j][k][0] = 0;
else gadd(f[i][j][k][0], 1);
//这个DP的起点条件并不一定是要满足ok(i,j)&&ok(i,k)&&ok(j,k)，因为这个状态可能是中途状态
if (f[i][j][k][0])
for (int u = 1; u < i; ++u)if (e[u][i])
gadd(f[u][j][k][2], f[i][j][k][0]);
if(f[i][j][k][2])
for (int u = 1; u < j; ++u)if (e[u][j])
gadd(f[i][u][k][1], f[i][j][k][2]);
if(f[i][j][k][1])
for (int u = 1; u < k; ++u)if (e[u][k])
gadd(f[i][j][u][0], f[i][j][k][1]);
【时间复杂度&&优化】
O(n^4)

巴特西

HDU5807分段dp

最新文章

热门文章