考虑转化一下问题
令
f(i,j,k)
表示从i到j恰好用了k步，并且到j的时候火车厢为空的方案数。
那么转移就是
f(i,j,k)=∑f(a,b,k1)∗f(c,j,k2)
，转移成立当且仅当存在i->a的边，载上货物x;b->c的边卸下货物x，k1+k2+2=k
但是这个DP时间复杂度是
O(E2k2)
，这个时候要引入一个新的函数
g(i,j,k)
，表示从i到j恰好用了k步，到j时车厢为空，且中途车厢从来没空过
那么转移就变成
f(i,j,k)=∑g(i,a,k1)∗f(a,j,k−k1)+∑f(b,j,k−1)
g(i,j,k)=∑f(a,b,k−2)
，其中存在i->a的边在上货物x，b->j的边卸下货物x，存在i->b的路径不需要载上或卸下货物。
这样每次转移就优化到
O(n4)
啦
那至于怎么求出原题的答案，原题解很抠，没有给出…
需要再引入一个函数
h(i,j,k)
，表示从i到j用了k步，但是车厢不一定为空的方案数…
转移还是
h(i,j,k)=∑g(i,a,k1)∗h(a,j,k−k1)+∑h(b,j,k−1)
因为神奇的g函数，这样转移的正确也就保证了……
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#define N 55
#define P 10007
#define foc(x,a) for(ITR x=a.begin();x!=a.end();x++)
using namespace std;
typedef pair<int,int> parii;
typedef vector<parii>::iterator ITR;
int n,m,K,Ans;
char A[100];
int f[N][N][N][2],g[N][N][N];
vector<parii> load[N][30],unload[N][30];
vector<parii> road[N],iroad[N];
inline void Read(){
gets(A);
int x,y,cnt; char c;
cnt=sscanf(A,"%d %d %c",&x,&y,&c);
if(cnt==2){
road[x].push_back(parii(x,y));
iroad[x].push_back(parii(x,y));
}
else if(c>='A'&&c<='Z'){
load[x][c-'A'].push_back(parii(x,y));
iroad[x].push_back(parii(x,y));
}
else unload[y][c-'a'].push_back(parii(x,y));
}
int main(){
scanf("%d%d%d",&n,&m,&K); gets(A);
for(int i=1;i<=m;i++) Read();
for(int i=1;i<=n;i++) f[i][i][0][0]=f[i][i][0][1]=1;
for(int k=1;k<=K;k++){
if(k>=2)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int t=0;t<26;t++)
foc(x,load[i][t]) foc(y,unload[j][t])
(g[i][j][k]+=f[x->second][y->first][k-2][0])%=P;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int s=0;s<2;s++){
if(s) foc(x,iroad[i]) (f[i][j][k][s]+=f[x->second][j][k-1][s])%=P;
else foc(x,road[i]) (f[i][j][k][s]+=f[x->second][j][k-1][s])%=P;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int s=0;s<2;s++)
for(int x=1;x<=n;x++)
for(int t=2;t<=k;t++)
(f[i][j][k][s]+=g[i][x][t]*f[x][j][k-t][s])%=P;
(Ans+=f[1][n][k][1])%=P;
}
return printf("%d\n",Ans),0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
