9.14

进行了一个 dp 套 dp 的学习。

Hero meet devil

solution

考虑 LIS 暴力 dp 的转移：令 \(f_{i,j}\) 表示第一个串考虑到第 \(i\) 个位置，第二个串考虑到第 \(j\) 个位置的 LIS 长度，那么有转移 \(f_{i,j}\leftarrow \max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+[s_i=t_j])\)，考虑维护这个 dp，令 \(g_{i,j}\) 表示构造了长度为 \(i\) 的答案串，其中 \(f_i\) 的状态为 \(j\) 的方案数。

状态 \(j\) 为一个数组 \(f_i\)，虽然这个数组值域很大，但是注意到相邻两项最多差 \(1\)，所以直接对 \(f_i\) 差分数组进行状压即可得到状态 \(j\)。

转移时枚举下一个位置的字符，考虑 \(f_i\) 增加这个字符后得到新的 \(f_{i+1}\) 数组状态是什么，这个可以预处理出来，即可得到答案。

时间复杂度 \(O(2^nm\left\lvert \Sigma \right\rvert)\)。

Code
#include
#include
#include
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
constexpr int N=1000+10;
constexpr int V=(1<<16)+10;
constexpr int inf=1e9+10;constexpr int mod=1e9+7;
inline int ad(int x,int y) {return ((x+y>=mod)?(x+y-mod):(x+y));}
inline void add(int &x,int y) {x=ad(x,y);}int n,m;
char s[N];
int a[N],ans[N];int nxt[V][5],f[2][V];
inline int calc(int s,int x) {static int g[20],h[20];g[0]=h[0]=0;f(i,1,n) g[i]=g[i-1]+((s>>(i-1))&1);f(i,1,n) {if (a[i]==x) h[i]=g[i-1]+1;else h[i]=max(h[i-1],g[i]);}int ret=0;f(i,1,n) if (h[i]>h[i-1]) ret|=(1<<(i-1));return ret;
}inline void solve() {scanf("%s",s+1);n=strlen(s+1);scanf("%d",&m);f(i,1,n) {if (s[i]=='A') a[i]=1;if (s[i]=='G') a[i]=2;if (s[i]=='T') a[i]=3;if (s[i]=='C') a[i]=4;}int S=(1<

【MX-X28-T4】「FAOI-R12」落花雨

solution

首先最终得到字符串的每个字符都会对应原串的一段区间。

注意到长度不小于 \(4\) 的串都能转化为一个 \(0\) 字符或一个 \(1\) 字符。

考虑如何判定一个串是否可以由原串变成，考虑贪心地去判定，也就是尽量靠前地进行匹配，但是这样不一定优秀，不过由上面的性质发现如果可以将原串 \([1,i]\) 变成这个串的前缀，那么最优变化方式一定会选一个长度在 \(i,i+1,i+2\) 中的前缀进行匹配。

于是考虑维护 \(f_{i,s}\) 表示答案串匹配了原串 \([1,i]\)，\(i+1,i+2\) 是否可以作为合法匹配位置的方案数，转移时枚举下一个需要的字符并找到第一个可以变成这个字符的位置即可。

时间复杂度线性。

Code
#include
#include
#include
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
constexpr int N=2e5+10;
constexpr int inf=1e9+10;constexpr int mod=998244353;
inline int ad(int x,int y) {return ((x+y>=mod)?(x+y-mod):(x+y));}
inline void add(int &x,int y) {x=ad(x,y);}inline void read(int &x) {x=0;char ch=getchar();while (ch<48) ch=getchar(); while (ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}int n;
char s[N];inline bool nor(bool x,bool y) {return !(x||y);}
inline int calc(int l,int r) {if (r-l+1>=4) return 3;if (l==r) return (1<<(s[l]-'0'));if (l+1==r) return (1< vec;vec.push_back(i);f(j,0,1) if ((s>>j)&1) vec.push_back(i+j+1);int flag_p=0;for (int pos:vec) flag_p|=(pos>n);if (flag_p) continue;f(k,0,1) {int nxt=0;for (int p:vec) F(x,6,1) if (p+x<=n&&(calc(p+1,p+x)>>k)&1) nxt|=(1<<(p+x-i));if (!nxt) continue;int mn=__builtin_ctz(nxt);int t=0;if ((nxt>>(mn+1))&1) t|=1;if ((nxt>>(mn+2))&1) t|=2;add(dp[i+mn][t],dp[i][s]);}if (i&&(n-i>=3||i==n||((s>>(n-i-1))&1))) ans+=dp[i][s];}printf("%d\n",(int)(ans%mod));f(i,0,n) f(s,0,3) dp[i][s]=0;
}int main() {int T;read(T);while (T--) solve();return 0;
}