题解：AT_arc119_f [ARC119F] AtCoder Express 3

Dovish · 2025-09-18 20:56:52 · 题解

~~不是这个题 AT*3600 为什么评紫啊。~~

分析

考虑对于一个固定的局面寻找一个简单的求答案方式，方便后边设状态。

观察样例上画的图，猜测在大部分情况下对于由 A，B 构成的连续段，只有首尾元素是可能出现在最短路径上的。尽管事实并非如此，但是这给了我们一些启发。

考虑在连续段都比较长的时候，我们可以构造一个策略：首先跳转到第二个连续段的起始，然后往回走一格，再向后跳到下下个连续段的起始。

反复这样跳转，直到走到终点为止。

容易手摸发现当某个连续段的长度 \le 3 时，这样就不一定是最优的了。

那怎么办？dp 呗！

发现，虽然对于每一格而言，可能会向前走导致直接对这个从前往后 dp 最小花费是不对的。但是对于连续段而言，一个位置，除了其作为一个连续段的开头跳转到上一个连续段的末尾这样来使得快速转移到下一个连续段。（其他情况下，向前走若干步之后再向后走都需要至少再走一遍向前跳的路的一部分，显然不优。）

考虑设 dp_i 表示走到第 i 个连续段的开头时，最小的花费。

转移考虑几种情况：

从上一个连通块起始端转移，向前跳一格再向后跳。总共 2 步。
如果上一个连通块长度是 1，则可以直接走到当前位置上，总共 1 步。
从上上个连通块起始走到末尾，再跳转到这里。一共需要 len 步。（len 是上上个连通块的长度）。发现通过手摸或者分讨前两步的转移，可以发现这里的 len 超过 3 时的转移都是无效的。

所以现在来整理一下，我们将这个 dp 作为内层状态来计数，需要记录的信息有：当前计算到序列上哪个位置，上一段的 dp 值，上上段的 dp 值，上上段的长度，上一段的颜色。

这五个信息中，由于 dp_{i-1}-dp_{i-2}\le 2，所以直接差分记录上上段的 dp 值即可。len 的限制上文说过了，只取 \le 3 的情况。故总状态是 O(nm) 的。

当然直接这么转移还需要记录上一段的长度，但是这么一来空间就开不下了，所以实现中对状态做了轻微调整：设 f_{i,j,k,l,c} 表示当前考虑了前 i 个位置，此时 dp_{i-1}+w 为 j，（w 是转移值，上一段长度为 1 时为 1，否则为 2），当前状态和上一个状态的转移到下一位的值的差：k=\max(0,dp_{i-1}+w-(dp_{i-2}+\operatorname{len_{i-2}}))。当前这一段的长度 l（>3 则记为 0），当前的颜色。

转移是 O(n^2m) 的，简单前缀和优化一下即可做到 O(nm)。

代码

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define fst first
#define sed second
#define Max(a,b) (a=max(a,b))
#define Min(a,b) (a=min(a,b))
using namespace std;
const int N=4000+10,M=1e6+10,inf=1e9,mod=1e9+7;
bool MS;int used;
inline void Add(int&u,int v){u=u+v>=mod?u+v-mod:u+v;}
inline void Dec(int&u,int v){u=u-v<0?u-v+mod:u-v;}
int n,m,a[N];
string s;
int dp[N][2010][3][4][2];//i,j,k,l,c
bitset<N>vis[2][N];
bool MT;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    int lim=m+2;
    n--;
    cin>>s;
    s=" "+s;
    rep(i,1,n)
    {
        if(s[i]=='?')a[i]=-1;
        else a[i]=s[i]-'A';
    }
    rep(c,0,1)
    rep(i,1,n)
    rep(j,i,n)
    {
        if(a[j]!=c&&a[j]!=-1)break;
        vis[c][i][j]=1;
    }
    dp[0][1][0][1][0]=dp[0][1][0][1][1]=1; 
    rep(i,1,n)
    {
        rep(c,0,1)//这一段的颜色 
        rep(pos,max(i-2,1),i)//这一段作为连通块
        if(vis[c][pos][i])
        rep(j,0,lim)
        rep(k,0,2)
        rep(l,0,3) 
        {
            int now=j-k+(i==pos?1:2);
            int nowk=max(0,now-(j-(l==1?1:2)+(l==0?inf:l)));
            if(pos-1)
            Dec(dp[i][now][nowk][i-pos+1][c],dp[pos-2][j][k][l][c^1]);
            Add(dp[i][now][nowk][i-pos+1][c],dp[pos-1][j][k][l][c^1]);
        }
        rep(c,0,1)
        {
            int pos=i-3;
            while(vis[c][pos][i])
            pos--;
            pos++;

            rep(j,0,lim)
            rep(k,0,2)
            rep(l,0,3)
            {
                int now=j-k+2;
                int nowk=max(0,now-(j-(l==1?1:2)+(l==0?inf:l)));
                if(i>=4)
                Add(dp[i][now][nowk][0][c],dp[i-4][j][k][l][c^1]);
                if(pos>=2)
                Dec(dp[i][now][nowk][0][c],dp[pos-2][j][k][l][c^1]);
            }
        }
        rep(c,0,1)//这一段的颜色 
        rep(j,0,lim)
        rep(k,0,2)
        rep(l,0,3) 
        Add(dp[i][j][k][l][c],dp[i-1][j][k][l][c]);
    }
    int ans=0;
    rep(j,0,lim)
    rep(c,0,1)
    rep(k,0,2)
    rep(l,0,3)
    {
        int now=j-k;//注意这是真实的dp值 
        if(now<=m)
        {
            Add(ans,dp[n][j][k][l][c]); 
            Dec(ans,dp[n-1][j][k][l][c]);   
        }
    }

    cout<<ans<<'\n';
    cerr<<"Memory:"<<(&MS-&MT)/1048576.0<<"MB Time:"<<clock()<<"ms\n";
}