题解 P7152 【[USACO20DEC] Bovine Genetics G】

· · 题解

Observation: 注意到一个非常重要的事实,由于我们是将所有连续相同字符之间的位置切开,因而对于一个串,它对应的结果串是唯一的。所以对于结果串而言,一种合法划分即对应一种合法初始串。

那么什么样的串是合法串呢？显然的有两个条件：

  1. 每一段划分中间不能有连续相同字符，不然我们一定会在那个位置将其割开。
  2. 对于划分中的连续两个子串s,t，s的首字符必须等于t的末字符，不然我们也不会去割那个位置。

不难证明这是一个充分必要条件。

由此可以得到一个朴素的DP想法，考虑dp[i][ch]表示已经把前i个字符割好了，且最后一个子串的首字母为ch，转移时从大往小枚举前一个划分位置j，判断s[j+1\ldots i]有无连续相同字符即可。这个东西的复杂度是\Theta(n^2)的，无法接受。

考虑优化。在这种划分问题中，有一个套路是考虑i时要么加入前一个划分，要么另起一段。这道题中也是同样的道理。令dp[i][a][b][c]表示最后一段最后一个字母为a，首字母为b，倒数第二段为c。

这样，对于s[i+1]来说，若s[i+1]!=a，那么自然可以添加进最后一段。若a=c，那么最后一段就可以结束，让s[i+1]自成一段。

这样复杂度即为\Theta(n)，转移时有一个|\Sigma|^4级别的常数，此题|\Sigma|为4，所以没有问题。

Code

#include<bits/stdc++.h>

#define y0 pmtx
#define y1 pmtxx
#define x0 pmtxxx
#define x1 pmtxxxx
#define pb push_back
#define mp make_pair
#define fi first 
#define se second
#define DEBUG printf("Passing Line %d in function [%s].\n",__LINE__,__FUNCTION__)

using namespace std;

typedef pair<int ,int > pii;
typedef vector<int > vi;
typedef long long ll;
typedef unsigned long long ull;

namespace FastIO{
    const int SIZE=(1<<20);
    char in[SIZE],*inS=in,*inT=in+SIZE;
    inline char Getchar(){
        if(inS==inT){inT=(inS=in)+fread(in,1,SIZE,stdin);if(inS==inT)return EOF;}
        return *inS++;
    }
    char out[SIZE],*outS=out,*outT=out+SIZE;
    inline void Flush(){fwrite(out,1,outS-out,stdout);outS=out;}
    inline void Putchar(char c){*outS++=c;if(outS==outT)Flush();}
    struct NTR{~NTR(){Flush();}}ztr;
}

#ifndef LOCAL
    #define getchar FastIO::Getchar
    #define putchar FastIO::Putchar 
#endif

template<typename T> inline void read(T &x){
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    x*=f;
}

template<typename T>inline void write(T x){
    if(!x)putchar('0');
    if(x<0)x=-x,putchar('-');
    static int sta[40];int tot=0;
    while(x)sta[tot++]=x%10,x/=10;
    while(tot)putchar(sta[--tot]+48);
}
const int maxn=200007,INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ll LINF=0x3f3f3f3f3f3f3f3fll;
const ll P=19260817;

template<typename T>inline void ckmax(T &x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T &x,T y){x=(y<x?y:x);}
template<typename T>inline T my_abs(T x){if(x<0)x=-x;return x;}
inline int mod1(int x){return x<MOD?x:x-MOD;}
inline int mod2(int x){return x<0?x+MOD:x;}
inline void add(int &x,int y){x=mod1(x+y);}
inline void sub(int &x,int y){x=mod2(x-y);}

char s[maxn];
int n;
int dp[maxn][4][4][4];
const char to[]="AGCT";
int ans=0;
int main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(s[1]=='?'||s[1]==to[j])dp[1][j][j][i]=1;
        }
    }
    for(int i=2;i<=n;i++){
        for(int a=0;a<4;a++){
            if(s[i]!='?'&&s[i]!=to[a])continue;
            for(int b=0;b<4;b++){
                for(int c=0;c<4;c++){
                    for(int la=0;la<4;la++){
                        if(la!=a)add(dp[i][a][b][c],dp[i-1][la][b][c]);
                        if(la==c)add(dp[i][a][a][b],dp[i-1][la][b][c]);
                    }
                }
            }
        }
    }
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            add(ans,dp[n][i][j][i]);
        }
    }
    printf("%d",ans);
    return 0;
}

//things to remember
//1.long long
//2.array length
//3.freopen
//4 boarder case

update on 2021.2.3:

鉴于评论区有很多人(确信)询问n^2的做法，我这里简单的描述一下，转移大概就是

dp[i][a]=\sum_{j< i,s[i]=b,s[j+1]=a} dp[j][b](\forall k\in [j+1,i),s[k]!=s[k+1])

转移时从大往小枚举k即可。