Codeforces 1163D Mysterious Code（AC自动机+DP）

用 AC自动机来做有点想不到，捞一手就是学一手。

设 dp[ i ][ j ] 表示字符串 c 中的第 i 位到字典树上节点 j 的最大值是多少， word[ j ] 表示在节点 j 下对答案修改的值是多少。

首先可以确定是 s 和 t 塞入字典树时，他们的结尾节点的 word 值显然一个是 1 一个是 -1 ，接下来就是 fail 数组上的一波操作，对于当前节点 j ，我们的 word[ j ] 需要加上 word[ fail[ j ] ] ，即当选到当前节点 j 时候，加上可能匹配到的一个完整的 s 或者一个完整的 t 的影响。假设 s = "baaaa" , t = "aa" ,当 j 节点在 s 下的第一个 ‘a' 时， fail[ j ] 在 t 的第一个 ‘a’ , word[ j ] 不进行修改，当 j 节点在 s 下的第二个 'a' 时， fail[ j ] 在 t 的第二个 ‘a' , word[ j ] 更新值为 word[ j ]-1 ,表示在匹配过程中到 s 的 "baa" 时，恰好也匹配到了一个 t ，我们需要减去一个完整的 t 带来答案的影响，同理，到 s 的第三个 ‘a’ 不修改， s 的第四个 'a' 修改为 word[ j ]-1 ，那么word就是这么个作用。

接下来转移方程就比较好理解了，设 id 为在节点 j 下的 ‘a' ~ ‘z’ 的任意一个节点值，显然只有在 c[ i ] 为匹配符或者 c[ i ] 恰好等于节点 j 下对应的字符才能进行转移，那么转移方程就是 dp[ i+1 ][ id ]=max(dp[ i+1 ][ id ],dp[ i ][ j ]+word[ id ]) ，最后只需要枚举在所有节点下的 i 等于 c.size() 的 dp 值取 max 就是答案了。

 //      ——By DD_BOND 

 //#include<bits/stdc++.h>

 #include<functional>

 #include<algorithm>

 #include<iostream>

 #include<sstream>

 #include<iomanip>

 #include<climits>

 #include<cstring>

 #include<cstdlib>

 #include<cstddef>

 #include<cstdio>

 #include<memory>

 #include<vector>

 #include<cctype>

 #include<string>

 #include<cmath>

 #include<queue>

 #include<deque>

 #include<ctime>

 #include<stack>

 #include<map>

 #include<set>

 #define fi first

 #define se second

 #define MP make_pair

 #define pb push_back

 #define INF 0x3f3f3f3f

 #define pi 3.1415926535898

 #define lowbit(a)  (a&(-a))

 #define lson l,(l+r)/2,rt<<1

 #define rson (l+r)/2+1,r,rt<<1|1

 #define Min(a,b,c)  min(a,min(b,c))

 #define Max(a,b,c)  max(a,max(b,c))

 #define debug(x)  cerr<<#x<<"="<<x<<"\n";

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> P;

 typedef pair<ll,ll> Pll;

 typedef unsigned long long ull;

 const ll LLMAX=2e18;

 const int MOD=1e9+;

 const double eps=1e-;

 const int MAXN=1e6+;

 inline ll sqr(ll x){ return x*x; }

 inline int sqr(int x){ return x*x; }

 inline double sqr(double x){ return x*x; }

 ll gcd(ll a,ll b){ return b==? a: gcd(b,a%b); }

 ll exgcd(ll a,ll b,ll &x,ll &y){ ll d; (b==? (x=,y=,d=a): (d=exgcd(b,a%b,y,x),y-=a/b*x)); return d; }

 ll qpow(ll a,ll n){ll sum=;while(n){if(n&)sum=sum*a%MOD;a=a*a%MOD;n>>=;}return sum;}

 inline int dcmp(double x){  if(fabs(x)<eps) return ;   return (x>? : -); }

 int tree[][],word[],fail[],cnt=,dp[][];

 void insert(string s,int v){

     int root=;

     for(int i=;i<(int)s.size();i++){

         int id=s[i]-'a';

         if(!tree[root][id]) tree[root][id]=++cnt;

         root=tree[root][id];

     }

     word[root]+=v;

 }

 void get_fail(){

     queue<int>q;

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

         if(tree[][i]){

             fail[tree[][i]]=;

             q.push(tree[][i]);

         }

     while(!q.empty()){

         int u=q.front();    q.pop();

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

             if(tree[u][i]){

                 fail[tree[u][i]]=tree[fail[u]][i];

                 q.push(tree[u][i]);

             }

             else    tree[u][i]=tree[fail[u]][i];

         word[u]+=word[fail[u]];

     }

 }

 int main(void)

 {

     ios::sync_with_stdio(false);    cin.tie();   cout.tie();

     int ans=-INF;  string c,s,t;   cin>>c>>s>>t;

     insert(s,);    insert(t,-);     get_fail();

     memset(dp,-INF,sizeof(dp));

     dp[][]=;

     for(int i=;i<(int)c.size();i++)

         for(int j=;j<=cnt;j++)

             for(int z=;z<;z++)

                 if(c[i]=='*'||'a'+z==c[i]){

                     int id=tree[j][z];

                     dp[i+][id]=max(dp[i+][id],dp[i][j]+word[id]);

                 }

     for(int i=;i<=cnt;i++)   ans=max(ans,dp[c.size()][i]);

     cout<<ans<<endl;

     return ;

 }

巴特西

Codeforces 1163D Mysterious Code（AC自动机+DP）

最新文章

热门文章