bzoj 1444: [Jsoi2009]有趣的游戏【AC自动机+dp+高斯消元】

https://blog.sengxian.com/solutions/bzoj-1444 orz

一直是我想错了，建出AC自动机之后，实际上这个定义是设f[i]为经过i节点的 * 期望次数 * ，因为单词末尾节点走到意味着游戏结束，所以经过单词末尾节点的概率就是经过单词末尾节点的期望次数。为什么是期望呢，因为概率的上限是1，不能随便转移

这样定义状态之后，得到dp转移为

\[f[i]=\sum_{pr节点可以通过字符c转移到i节点}p[c]*f[pr]
\]

因为是期望，所以root节点右边要加1

然后移项做高斯消元即可

#include<iostream>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

const int N=105;

int n,l,m,c[N][15],tot=1,fa[N],va[N],fl,id[N];

double p[N],a[N][N],d[N];

char s[N];

void gaosi(int n)

{

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

	{

		int nw=i;

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

			if(fabs(a[nw][i])<fabs(a[j][i]))

				nw=j;

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

			swap(a[nw][j],a[i][j]);

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

			a[i][j]/=a[i][i];

		a[i][i]=1;

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

		{

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

				a[j][k]-=a[j][i]*a[i][k];

			a[j][i]=0;

		}

	}

	for(int i=n-1;i>=1;i--)

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

			a[i][n+1]-=a[j][n+1]*a[i][j];

}

int main()

{

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

	for(int i=0,x,y;i<m;i++)

	{

		scanf("%d%d",&x,&y);

		p[i]=(double)x/(double)y;

	}

	for(int ca=1;ca<=n;ca++)

	{

		scanf("%s",s+1);

		int nw=1,f=0;

		for(int i=1;i<=strlen(s+1);i++)

		{

			if(p[s[i]-'A']<1e-8)

				f=1;

			if(!c[nw][s[i]-'A'])

				c[nw][s[i]-'A']=++tot;

			nw=c[nw][s[i]-'A'];

		}

		va[nw]=1;

		id[ca]=tot;//cerr<<id[ca]<<endl;

		fl+=f;

	}

	if(fl==n)

	{

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

			puts("0.00");

		return 0;

	}

	queue<int>q;

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

		if(c[1][i])

			fa[c[1][i]]=1,q.push(c[1][i]);

		else

			c[1][i]=1;

	while(!q.empty())

	{

		int u=q.front();

		q.pop();

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

			if(c[u][i])

				fa[c[u][i]]=c[fa[u]][i],q.push(c[u][i]);

			else

				c[u][i]=c[fa[u]][i];

	}

	a[1][1]=-1,a[1][tot+1]=-1;

	for(int i=1;i<=tot;i++)

	{

		if(i>1)

			a[i][i]--;

		if(va[i])

			continue;

		for(int j=0;j<m;j++)

			a[c[i][j]][i]+=p[j];

	}//cerr<<tot<<endl;

	gaosi(tot);

	// for(int i=1;i<=tot;i++)

	// {

		// for(int j=1;j<=tot+1;j++)

			// cerr<<a[i][j]<<" ";

		// cerr<<endl;

	// }

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

		printf("%.2f\n",a[id[i]][tot+1]/a[id[i]][id[i]]);

	return 0;

}

巴特西

bzoj 1444: [Jsoi2009]有趣的游戏【AC自动机+dp+高斯消元】

最新文章

热门文章