3214: [Zjoi2013]麗潔體

Time Limit: 10 Sec??Memory Limit: 512 MB
Submit: 906??Solved: 335
[Submit][Status][Discuss]

Description

平時的練習(xí)和考試中，我們經(jīng)常會碰上這樣的題：命題人給出一個例句，要我們類比著寫句子。這種往往被稱為仿 寫的題，不單單出現(xiàn)在小學(xué)生的考試中，也有時會出現(xiàn)在中考中。許多同學(xué)都喜歡做這種題，因?yàn)檩^其它題顯得有 趣。仿寫的句子往往具有“A__B__C”的形式，其中A，B，C是給定的由一個或多個單詞組成的短句，空的部分需要 學(xué)生填寫。當(dāng)然，考試的時候空在那里也是可以的。例如，“其實(shí)天不暗陰云終要散，其實(shí) ，其實(shí) ，其實(shí)路不遠(yuǎn) 一切會如愿，艱難困苦的日子里我為你祈禱，請你保重每一天”。再比如，“見了大海的洶涌，沒見過大山的巍峨 ，真是遺憾；見了大山的巍峨，沒見過 ，還是遺憾。出發(fā)吧，永遠(yuǎn)出發(fā)。 ，人有不老的心情。”由于現(xiàn)在是網(wǎng)絡(luò) 時代，我們不再只能仿寫命題人命的題，我們可以仿寫網(wǎng)上各種句子和段落。2011年3月26日，某人在博客上發(fā)布 了的消息就惹來了很多人的仿寫。? 很難過吧。。。考得完爆了。。。? 。。。。。。其實(shí)也沒什么可以說的。。。都是蒟蒻的借口罷了。。。? 。。。自己果然還只是半吊子水平呢。。。。? 。。。祝大家都能進(jìn)省隊(duì)。。。其實(shí)只要不要有遺憾就好了呢。。。? 雖然我很遺憾或許不能走下去了。。。。。? 886? 在網(wǎng)絡(luò)上廣泛流傳的仿寫，因?yàn)樵谀承┑胤接歇?dú)到之處，大都被命名為“某某體”。打開人人，刷新微博，你也能 發(fā)現(xiàn)這樣和那樣的體，比如，對不起體，**說明他愛你體等等。金先生注意到了這一現(xiàn)象，他敏銳地認(rèn)為這是一個 很有價值的研究課題，于是就其展開研究，打算發(fā)一篇paper。由于在網(wǎng)上發(fā)消息，人們有了更大的靈活度，人們 有時因?yàn)楸磉_(dá)的需要，還往原本固定的A, B, C中添加一些修飾的詞語。這就給辨別一個句子或段落是否是另一個 句子或段落的仿寫增加了困難。金先生現(xiàn)在研究一種形如“A*B*C”的體作品，其中A, B, C分別是某個由若干單詞 組成的短句，*代表0個或多個單詞。他在網(wǎng)上找了大量的體作品，不過很多體作品不太合乎原作者的格式，也就是 相當(dāng)于在正規(guī)的體作品中插入了0個或多個單詞。由于數(shù)據(jù)量太大，金先生無法一個一個看過去，于是想請你幫忙 ，去掉盡量少的單詞，使它成為指定的體。

Input

包含4行。? 第一行是某個也許不規(guī)范的體作品T，? 接下來三行分別代表A, B, C。 1≤|T|, |A|, |B|, |C|≤50000；所有單詞長度不超過5，出現(xiàn)次數(shù)不超過500；數(shù)據(jù)保證答案總存在

Output

僅一行，包含一個數(shù)，即最少的去除單詞數(shù)。

Sample Input

xiang yao yi zhi ai zhe mou wu de hua yi yao guai zhi si lai shuo tai chang le xiang yao shi xian yi qie meng xiang de hua yi ren lei zhi sheng lai shuo tai duan le
yao
tai chang le yao
tai duan le

Sample Output

2
【樣例說明】
在上述樣例中，不規(guī)范的體作品為：“想要一直愛著某物的話，以妖怪之死來說太長了；想要實(shí)現(xiàn)一切夢想的話，以人類之生來說太短了”。
規(guī)范的體形如：“要*太長了要*太短了”。
修改后的規(guī)范的體為：“要一直愛著某物的話，以妖怪之死來說太長了；要實(shí)現(xiàn)一切夢想的話，以人類之生來說太短了”。

HINT

Source

[Submit][Status][Discuss]

單詞長度不超過5顯然就是給我們哈希的，這樣就成了字符匹配問題了。

“A和C貪心即可，B在中間枚舉搞一搞就好了”

然而發(fā)現(xiàn)并不會搞一搞。

f[i]表示到當(dāng)前為止最靠右的b[i]在哪里，g[i]表示到此為止最少要刪多少個單詞，每次轉(zhuǎn)移更新一次答案，正確性不難證。

感覺就是先想出一個感覺很不靠譜的做法，然后證明它是靠譜的。

拉鏈哈希很不熟啊。

1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define rep(i,l,r) for (int i=l; i<=r; i++) 5 using namespace std; 6 7 const int N=100100,inf=0x3f3f3f3f,P=2010527; 8 int n,la,lb,lc,i,j,k,l,r,nd,sum,ans=inf,s[N],a[N],b[N],c[N]; 9 int v[N],nxt[N],Nxt[N],h[N],H[P],f[N],g[N]; 10 11 int Hash(int x){ 12 int y=H[x%P]; 13 while (v[y]!=x && y) y=Nxt[y]; 14 if (v[y]==x) return y; 15 v[++nd]=x; Nxt[nd]=H[x%P]; H[x%P]=nd; 16 return nd; 17 } 18 19 int find(int x){ 20 int y=H[x%P]; 21 while (v[y]!=x && y) y=Nxt[y]; 22 return y; 23 } 24 25 void getstr(int s[],int &n){ 26 int x=0; char ch=getchar(); 27 for (; ch!='\n'; ch=getchar()) 28 if (ch>='a' && ch<='z') x=x*26+ch-'a'; 29 else s[++n]=x,x=0; 30 if (x) s[++n]=x; 31 } 32 33 int main(){ 34 freopen("bzoj3214.in","r",stdin); 35 freopen("bzoj3214.out","w",stdout); 36 getstr(s,n); getstr(a,la); getstr(b,lb); getstr(c,lc); 37 for (i=1; i<=lb; i++) k=Hash(b[i]),nxt[i]=h[k],h[k]=i; 38 for (l=i=1; i<=la; l++) if (s[l]==a[i]) i++; else sum++; 39 for (r=n,i=lc; i; r--) if (s[r]==c[i]) i--; else sum++; 40 memset(g,0x3f,sizeof(g)); 41 for (i=l; i<=r; i++){ 42 for (j=h[find(s[i])]; j; j=nxt[j]) 43 if (j==1) f[1]=i,g[1]=0; 44 else if (f[j-1]) f[j]=i,g[j]=g[j-1]+i-f[j-1]-1; 45 ans=min(ans,g[lb]); 46 } 47 printf("%d\n",ans+sum); 48 return 0; 49 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/HocRiser/p/8761159.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ3214][ZJOI2013]丽洁体(Hash+DP)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。