HDU 4534 郑厂长系列故事——新闻净化(AC自动机+DP)
题目：给出一些模式串，其中有一些串必须出现在子串当中，有一些串是不可以出现在子串中。然后还有一些串有一些分值。给出母串，问最少需要删除多少个字母，能够满足条件，然后使得分值尽可能大。
妥妥的AC自动机+DP啊。
复赛第一场，妥妥的上来做了签到题之后就开始开E题了，然后就没有然后了。。。
AC自动机都能写错，妥妥地WA了几十次啊
每次建fail的时候，都要把val,canot,must进行转移啊，我SB了只转移了val
del[i][j][k],pot[i][j][k]表示前i个字符，当前在自动机中的j结点，必取串的状态为k时的最优情况。
[cpp]
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<stack>
#include<string>
#include<ctime>
#include<queue>
#include<cassert>
#define inf 0x11111111
#define maxn 210005
#define eps 1e-8
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000007
#define sqr(a) ((a)*(a))
#define Key_value ch[ch[root][1]][0]
#define test puts("OK");
#define pi acos(-1.0)
#define lowbit(x) ((-(x))&(x))
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int M=1610;
struct Trie {
Trie *next[26];
Trie *fail;
int must,canot;
int val,word,kind;
};
Trie *que[M],s[M];
int idx,tot,pre[105];
Trie *NewNode() {
Trie *tmp=&s[idx];
mem(tmp->next,NULL);
tmp->must=tmp->canot=tmp->val=0;
tmp->fail=NULL;
tmp->kind=idx++;
return tmp;
}
void Insert(Trie *root,char *s,int len,int k,int val) {
Trie *p=root;
for(int i=0; i<len; i++){
if(p->next[s[i]-'a']==NULL) p->next[s[i]-'a']=NewNode();
p=p->next[s[i]-'a'];
}
if(val==999) {p->must|=1<<tot;tot++;}
else if(val==-999) p->canot|=1;
else p->val+=val;
}
void Bulid_fail(Trie *root) {
int head=0,tail=0;
que[tail++]=root;
root->fail=NULL;
while(head<tail){
Trie *tmp=que[head++];
for(int i=0; i<26; i++){
if(tmp->next[i]){
if(tmp==root) tmp->next[i]->fail=root;
else{
Trie *p=tmp->fail;
while(p!=NULL){
if(p->next[i]){
tmp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) tmp->next[i]->fail=root;
}
if(tmp->next[i]->fail->val) tmp->next[i]->val+=tmp->next[i]->fail->val;
if(tmp->next[i]->fail->must) tmp->next[i]->must|=tmp->next[i]->fail->must;
if(tmp->next[i]->fail->canot) tmp->next[i]->canot|=1;
que[tail++]=tmp->next[i];
}
else if(tmp==root) tmp->next[i]=root;
else tmp->next[i]=tmp->fail->next[i];
}
}
}
char str[105];
int del[2][M][1<<8];
