[图论][动态规划][ZROI训练]归来

####题目描述:
小A在8102年掌握了穿越时间的科技，他想要回归遥远的2018年来看一看。

我们定义“时间线”是长度恰好为 $n$ ，仅由 ABCD 四个大写字母组成的字符串。

设某个时间线为 $S$，小A可以用以下两种方式修改时间线：

交换 $S$ 中相邻两个字符。
使用某种转移。一个转移是两个长度不超过 $n$ 的等长字符串 $(Ai,Bi)$，可以把 $S$ 中某个子串 $A_i$ 替换成 $Bi$。
小A自然能随意行走于时间线上，但他想享受这跃迁的过程。他想考考你：初始的时间线任选，任意操作，在任意一条时间线结束，途中经过的不同时间线数量最多是多少？

注意可以经过重复的时间线，但只会计入一次答案。

####输入格式
第一行两个数 $n$ , $m$，表示时间线的长度和转移的个数。

后面 $m$ 行，每行两个等长字符串 $Ai$, $Bi$，表示一个转移。

####输出格式
一行，一个整数表示最大答案。

####限制与约定
对于 $30\%$ 的数据， $n≤5$, $m≤5$.
对于 $50\%$ 的数据， $n≤10$, $m≤30$.
对于 $100\%$ 的数据， $n≤30$, $m≤50$.

----------
###题解:
暴力没思路,考试最后30s才调对反杀,吓得不轻qwq
观察一下可以发现,一个串里每个字母的顺序并不影响,因为可以交换字符串中相邻两个字符,所以只有ABCD的个数才是关键.
每个转移可以看成用一些数量的ABCD换取等量的ABCD,这样,在所有状态之间就形成了一些有向的转移.
我们用一个四元组$(a,b,c,d)$来表示每个状态,因为字符串长度为$n$,所以就有$a+b+c+d\leq n$的限制.这样我们发现即使是极限数据状态数量也不会超过6000.
那么接下来就可以根据交换等量字母的规则来连边了.这里最好用map把每个四元组映射成一个整数,处理起来会方便一些.
现在.
所以对于一个状态$i$的转移方程就是:
$$f[i]=\max(f[j])+cnt[i]$$
$$cnt[i]=C_{a+b+c+d}^a*C_{b+c+d}^b*C_{c+d}^c$$
其中, $j$ 枚举的是 $i$ 可以到达的状态, $cnt[i]$ 是 $i$ 这个状态可以组成字符串的方案总数.
但是,处理完之后的图不一定是一个有向无环图,所以我们还要用Tarjan进行缩点之后,处理出拓扑序列,在按照拓扑序进行转移即可.

----------

贴上代码:
```
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<stack>
#include<string.h>
#include<queue>
#include<map>
#define maxn 100005
#define maxm 40000005
#define ll long long
using namespace std;
struct ch{int f1[5],f2[5];}ex[maxn];
struct s{int a,b,c,d;};
bool operator<(s a,s b){return a.a==b.a?(a.b==b.b?(a.c==b.c?a.d<b.d:a.c<b.c):a.b<b.b):a.a<b.a;}
int n,m;
map<s,int> ac;
map<int,s> tc;
ll ans=0,sum[maxn],dp[maxn],tseq[maxn];
ll C[300][300];
int to[maxm],pre[maxm],las[maxm],deg[maxn],tot,nid;
int be[maxn],in[maxn],dfn[maxn]={0},low[maxn],t=0,scc=0;
vector<int> ha[maxn];
stack<int> st;
queue<int> q;
void ins(int a,int b)
{
	pre[++tot]=las[a];
	las[a]=tot,to[tot]=b;
}
void Tarjan(int x)
{
	in[x]=1;
	dfn[x]=low[x]=++t;
	st.push(x);
	for(int i=las[x];i;i=pre[i])
	{
		int y=to[i];
		if(!dfn[y]) Tarjan(y),low[x]=min(low[x],low[y]);
		else if(in[y]) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]!=low[x])return;
	++scc;
	while(1)
	{
		int u=st.top();
		st.pop(),in[u]=0,be[u]=scc;
		ha[scc].push_back(u);
		if(u==x)return;
	}
}
int cmp(int a,int b){return a>b;}
ll getarr(ll a,ll b,ll c,ll d)
{
	return C[a+b+c+d][a]*C[b+c+d][b]*C[c+d][c];
}
int inq[maxn];
void solve()
{
	int p=0;
	while(q.size())
	{
		int t=q.front();
		q.pop();
		tseq[++p]=t,inq[t]=0;
		for(int i=0;i<ha[t].size();i++)
			for(int j=las[ha[t][i]];j;j=pre[j])
				if(be[to[j]]!=t)
				{
					deg[be[to[j]]]--;
					if(deg[be[to[j]]]==0&&!inq[be[to[j]]]) q.push(be[to[j]]),inq[be[to[j]]]=1;
				}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	C[0][0]=C[1][0] = C[1][1] = 1;
	for (int i = 2; i <=n*2; i++)
	{
		C[i][0] = 1;
		for (int j = 1; j<=n*2; j++)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]);
	}
	for(int i=1;i<=m;i++)
	{
		char s1[50],s2[50];
		scanf("%s%s",s1+1,s2+1);
		int len=strlen(s1+1); 
		for(int j=1;j<=len;j++) ex[i].f1[s1[j]-'A'+1]++;
		for(int j=1;j<=len;j++) ex[i].f2[s2[j]-'A'+1]++;
	}
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			for(int k=0;k<=n;k++)
				for(int l=0;l<=n;l++)
				{
					if(i+j+k+l!=n) continue;
					tc[++nid]=(s){i,j,k,l};
					ac[(s){i,j,k,l}]=nid;
				}
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			for(int k=0;k<=n;k++)
				for(int l=0;l<=n;l++)
				{
					if(i+j+k+l!=n) continue;
					for(int id=1;id<=m;id++)
					{
						if(i-ex[id].f1[1]<0||j-ex[id].f1[2]<0||k-ex[id].f1[3]<0||l-ex[id].f1[4]<0) continue;
						int ti=i-ex[id].f1[1],tj=j-ex[id].f1[2],tk=k-ex[id].f1[3],tl=l-ex[id].f1[4];
						ti+=ex[id].f2[1],tj+=ex[id].f2[2],tk+=ex[id].f2[3],tl+=ex[id].f2[4];						ins(ac[(s){i,j,k,l}],ac[(s){ti,tj,tk,tl}]);
					}
				}
	for(int i=1;i<=nid;i++) if(!dfn[i]) Tarjan(i);
	for(int i=1;i<=scc;i++)
	{
		for(int j=0;j<ha[i].size();j++)
		{
			s t=tc[ha[i][j]];
			sum[i]+=getarr(t.a,t.b,t.c,t.d);
			for(int k=las[ha[i][j]];k;k=pre[k])
				if(be[to[k]]!=be[ha[i][j]]) deg[be[to[k]]]++;
		}
	}
	for(int i=1;i<=scc;i++) if(deg[i]==0) q.push(i);
	solve();
	for(int i=scc;i>=1;i--)
	{
		int id=tseq[i];
		dp[id]+=sum[id];
		ll mmax=0;
		for(int j=0;j<ha[id].size();j++)
			for(int k=las[ha[id][j]];k;k=pre[k])
				if(be[to[k]]!=be[ha[id][j]])
					mmax=max(mmax,dp[be[to[k]]]); 
		dp[id]+=mmax;
		ans=max(ans,dp[id]);
	}
	printf("%lld",ans);
}
```

PhantasmDragon 's Blog