域名价格查询网站,网站视频源码地址,一站式平台网站开发技术,wordpress调查插件题目描述 小豆参加了\(NOI\)的游园会#xff0c;会场上每完成一个项目就会获得一个奖章#xff0c;奖章 只会是\(N\), \(O\), \(I\)的字样。在会场上他收集到了\(K\)个奖章组成的串。 兑奖规则是奖章串和兑奖串的最长公共子序列长度为小豆最后奖励的等级。 现在已知兑奖串长度…题目描述 小豆参加了\(NOI\)的游园会会场上每完成一个项目就会获得一个奖章奖章 只会是\(N\), \(O\), \(I\)的字样。在会场上他收集到了\(K\)个奖章组成的串。 兑奖规则是奖章串和兑奖串的最长公共子序列长度为小豆最后奖励的等级。 现在已知兑奖串长度为\(N\)并且在兑奖串上不会出现连续三个奖章为\(NOI\)即奖章中不会出现子串\(NOI\)。 现在小豆想知道各个奖励等级会对应多少个不同的合法兑奖串。 题解 我们可以先考忽略那些奇奇怪怪的限制条件直接考虑如何统计序列数。 我们先考虑\(LCS\)的dp方法。\[ dp[i][j]max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1](s[i]t[j])) \] 我们如果把第二维单独拿出来考虑我们可以发现第二维是一个单调不降的数列而且前后两项的差是小于等于1的。 因为第二维的长度非常小所以我们可以把第二维差分之后状压起来作为我们的状态。 而且有一个好处我们知道了这个状态就能发当前\(dp\)值还原出来假设我们知道了下一个字符时什么我们就可以知道转移后的状态是什么了。 所以我们预处理\(g[i][j]\)表示当前状态为\(i\)新加入字符为\(j\)能够转移的状态。 然后我们再设\(dp[i][j][k]\)表示做到第\(i\)为当前状态为\(j\)匹配到k个字符(这个是判断那个特殊限制用的)随便转移一下就好了。 代码 #includeiostream
#includecstdio
#includecstring
using namespace std;
const int mod1e97;
int tran[200],g[3][116],dp[2][116][3],n,k,nw[20],a[20],ma,ans[20];
char s[20];
inline int rd(){int x0;char cgetchar();bool f0;while(!isdigit(c)){if(c-)f1;cgetchar();}while(isdigit(c)){x(x1)(x3)(c^48);cgetchar();}return f?-x:x;
}
inline void MOD(int x){xxmod?x-mod:x;}
int main(){nrd();krd();tran[N]0;tran[O]1;tran[I]2;scanf(%s,s1);for(int i1;ik;i)a[i]tran[(int)s[i]];ma(1k1);for(int o0;o3;o){for(int i0;ima;i){for(int j0;jk;j){nw[j](i(1j))!0;if(j)nw[j]nw[j-1]; }for(int jk;j1;--j){nw[j]max(nw[j],nw[j-1]);if(a[j]o)nw[j]max(nw[j],nw[j-1]1);}for(int j1;jk;j)nw[j]max(nw[j],nw[j-1]);int s0;for(int jk;j1;--j)nw[j]nw[j]-nw[j-1];for(int j0;jk;j)s|(1j)*nw[j];g[o][i]s;}}int now1,pre0;dp[now][0][0]1;for(int i0;in;i){swap(now,pre);memset(dp[now],0,sizeof(dp[now]));for(int j0;jma;j)for(int l0;l3;l)if(dp[pre][j][l])for(int p0;p3;p){int no(pl)?l1:(p0); if(no3)continue;MOD(dp[now][g[p][j]][no]dp[pre][j][l]);}}for(int i0;ima;i){for(int j0;jk;j){nw[j](i(1j))!0;if(j)nw[j]nw[j-1];} MOD(ans[nw[k]](1ll*dp[now][i][0]dp[now][i][1]dp[now][i][2])%mod);} for(int i0;ik;i)printf(%d\n,ans[i]);return 0;
} 转载于:https://www.cnblogs.com/ZH-comld/p/10554475.html
