【noi2019集训题1】脑部进食期望dp+高斯消元

题目大意：有n个点，m条有向边，每条边上有一个小写字母。

有一个人从1号点开始在这个图上随机游走，游走过程中他会按顺序记录下走过的边上的字符。

如果在某个时刻，他记录下的字符串中，存在一个子序列和S2相同，或者存在一个子串和S1相同，那么他就会当场去世。

他想知道他会不会当场去世，如果会，他想问你当场去世的时间的期望。

数据范围：n≤20，|S1|≤10，|S2|≤50

我们考虑列一个dp方程出来

设f[i][j][k]表示这人从1号点出发，当前走到i号点，且子串覆盖了S1的前j位，覆盖了S2的前k位的期望步数

然后你会发现你做不出来，因为最终根本无法统计答案（然后你就进死胡同了）

我们尝试把整个方程反过来

设$f[i][j][k]$表示你从$i$号点出发，之前走的路已经覆盖了$S1$的前$j$位，$S2$串的前$k$位的情况下，期望走多少部后会去世。

最终需要求的答案显然是$f[1][0][0]$

我们不难列出$f[i][j][k]=1+\frac{1}{d[i]} \sum\limits_{(i,u)∈E}f[u][j'][k']$

其中$d[i]$表示$i$号点的出度，$E$表示边集，$j'$和$k'$的具体值视该转移边的字母而订，非常好求。

这个方程我们显然可以通过高斯消元求解，时间复杂度$O(n^3|S1|^3|S2|^3)$，愉快$TLE$

无解的情况出现即为某一条方程出现了被零除。

我们发现，从$f[i][j'][k']$向$f[i][j][k]$转移的过程中，有$k'≥k$

那么我们显然可以固定$k$，对每一个$k$做一次高斯消元，然后向下一层传值，再高斯消元即可。

时间复杂度于是就降低到$O(n^3|S1|^3|S2|)$了

看起来有$4$个亿

实际上因不明原因，每一层需要转移的节点数根本就去不到理论上届

所以只跑了不到$20ms$（大雾）

 #include<bits/stdc++.h>

 #define M 205

 #define eps 1e-6

 using namespace std;

 double f[M][M]={},ans[M]={};

 void gauss(int n){

     for(int i=;i<=n;i++){

         int id=i;

         for(int j=i;j<=n;j++) if(f[id][i]<f[j][i]) id=j;

         swap(f[i],f[id]);

         if(fabs(f[i][i])<eps) {printf("-1\n"); exit();}

         for(int j=i+;j<=n;j++){

             double cha=f[j][i]/f[i][i];

             for(int k=i;k<=n+;k++) f[j][k]-=f[i][k]*cha;

         }

     }

     for(int i=n;i;i--){

         for(int j=i+;j<=n;j++) f[i][n+]-=ans[j]*f[i][j];

         ans[i]=f[i][n+]/f[i][i];

     }

 }

 struct edge{int u,next;char v;}e[]={}; int head[M]={},use=;

 void add(int x,int y,char z){use++;e[use].u=y;e[use].v=z;e[use].next=head[x];head[x]=use;}

 int n,m;

 char w[M]={},p[M]={}; int lenw,lenp;

 int nxt[M]={};

 void upd(char C,int id,int &nowj,int &nowk){

     for(;nowj&&w[nowj+]!=C;nowj=nxt[nowj]);

     if(w[nowj+]==C) nowj++;

     if(p[nowk+]==C) nowk++;

 }

 int vis[][][]={};

 void dfs(int i,int j,int k){

     if(vis[i][j][k]) return;

     vis[i][j][k]=;

     if(j==lenw||k==lenp) return;

     for(int l=head[i];l;l=e[l].next){

         char C=e[l].v; int id=e[l].u;

         int nowj=j,nowk=k;

         upd(C,id,nowj,nowk);

         dfs(id,nowj,nowk);

     }

 }

 int id[][]={},iid[][]={},cnt=; double d[M]={};

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++){

         int x,y; char z[]; scanf("%d%d%s",&x,&y,z);

         add(x,y,z[]); d[x]++;

     }

     scanf("%s",w+); lenw=strlen(w+);

     scanf("%s",p+); lenp=strlen(p+);

     for(int i=,j=;i<=n;i++){

         for(;j&&w[j+]!=w[i];j=nxt[j]);

         if(w[j+]==w[i]) j++;

         nxt[i]=j;

     }

     dfs(,,);

     for(int k=lenp-;~k;k--){

         int cnt=;

         for(int i=;i<=n;i++)

         for(int j=;j<lenw;j++){

             id[i][j]=;

             if(vis[i][j][k])

             id[i][j]=++cnt;

         }

         memset(f,,sizeof(f));

         for(int i=;i<=n;i++)

         for(int j=;j<lenw;j++) if(id[i][j]){

             int ID=id[i][j];

             f[ID][ID]=d[i];

             f[ID][cnt+]=d[i];

             for(int l=head[i];l;l=e[l].next){

                 char C=e[l].v; int u=e[l].u;

                 int nowj=j,nowk=k;

                 upd(C,u,nowj,nowk);

                 if(nowj==lenw) continue;

                 if(nowk==k){

                     f[ID][id[u][nowj]]--;

                 }else{

                     f[ID][cnt+]+=ans[iid[u][nowj]];

                 }

             }

         }

         memcpy(iid,id,sizeof(id));

         memset(ans,,sizeof(ans));

         gauss(cnt);

     }

     printf("%.10lf\n",ans[]);

 }

巴特西

【noi2019集训题1】脑部进食期望dp+高斯消元

最新文章

热门文章

巴特西

【noi2019集训题1】 脑部进食 期望dp+高斯消元

最新文章

热门文章

【noi2019集训题1】脑部进食期望dp+高斯消元