网站做项目,网站设计公司深,wordpress 评论 图片不显示,岳阳网站建设哪里有做不出来杂题,到处找题做 看到$loj$上新出了一道题,觉得很神仙不错, 还记得Censoring吗(一个AC自动机的题) 这个题求最优解,数据范围$150$ 题解 数据范围非常小,首先贪心肯定不行,考虑AC自动机上$dp$? 好吧其实是区间$dp$ 一个直接的想法是维护$f[l][r]0/1$表示是否可以清空$l… 做不出来杂题,到处找题做 看到$loj$上新出了一道题,觉得很神仙不错, 还记得Censoring吗(一个AC自动机的题) 这个题求最优解,数据范围$150$ 题解 数据范围非常小,首先贪心肯定不行,考虑AC自动机上$dp$? 好吧其实是区间$dp$ 一个直接的想法是维护$f[l][r]0/1$表示是否可以清空$l$,$r$这一段子段 然而转移起来很难转移,考虑再定义一个数组$g[l][r][i][w]0/1$表示是否可以清成第$i$个模式串的前$w$位 考虑$g$转移, 1.直接匹配$g[l][r][i][w]|g[l][r-1][i][w-1]$其中主串$str[r]c[i][w]$表示若$l,r-1$可以清成第$i$个模式串前$w-1$位那么若当前两个可以匹配上必然$l,r$可以清成第$i$个模式串前$w$位 2.由几部分拼凑$g[l][r][i][w]|g[l][q-1][i][w]\f[q][r]$表示$q-r$被清空那么$g$显然可以转移 那么根据$f$定义$f[l][r]|g[l][r][i][len[i]]$ 举个例子$momooo$ 模式串$moo$ 先$g[3][5][1][3]1$,得$f[3][5]1$得$g[1][5][1][2]1$(由$f[3][5]$)转移 再进行一步匹配$f[3][6][1][3]1$得$f[1][6]1$可以全部清空 那么$ans$根据类似最长上升子序列求 $ans[i]min(ans[i-1]1,ans[l-1](f[l][i]1))$两层循环枚举 考虑炸内存? 状压,怎么状压,压掉一维,这里不再解释,因为数据点足够水,这已经足以通过测试点 代码 #includebits/stdc.h
using namespace std;
#define A 152
#define ll long long
ll len[A],ans[A];
bool f[A][A],g[A][A][52][52];
ll n,cnt;
char c[A][A],str[A];
int main(){scanf(%s,str1);nstrlen(str1);scanf(%lld,cnt);for(ll i1;icnt;i){scanf(%s,c[i]1);len[i]strlen(c[i]1);}for(ll i1;in;i){f[i][i-1]1;for(ll j1;jcnt;j){g[i][i-1][j][0]1;}}for(ll k1;kn;k){//枚举当前长度for(ll l1;ln-k1;l){ll rlk-1;for(ll w1;wcnt;w){for(ll now1;nowlen[w];now){if(c[w][now]str[r])g[l][r][w][now]|g[l][r-1][w][now-1];}for(ll now1;nowlen[w];now){for(ll il;ir;i){g[l][r][w][now]|g[l][i-1][w][now]f[i][r];}}}for(ll w1;wcnt;w)f[l][r]|g[l][r][w][len[w]];}}for(ll i1;in;i){ans[i]ans[i-1]1;for(ll j1;ji;j){if(f[j][i]){ans[i]min(ans[i],ans[j-1]);}}}printf(%lld\n,ans[n]);
} View Code 转载于:https://www.cnblogs.com/znsbc-13/p/11579220.html
