HDU 4534 郑厂长系列故事――新闻净化(AC自动机+DP) - c++编程基础

题目：给出一些模式串，其中有一些串必须出现在子串当中，有一些串是不可以出现在子串中。然后还有一些串有一些分值。给出母串，问最少需要删除多少个字母，能够满足条件，然后使得分值尽可能大。

妥妥的AC自动机+DP啊。
复赛第一场，妥妥的上来做了签到题之后就开始开E题了，然后就没有然后了。。。
AC自动机都能写错，妥妥地WA了几十次啊
每次建fail的时候，都要把val,canot,must进行转移啊，我SB了只转移了val
del[i][j][k],pot[i][j][k]表示前i个字符，当前在自动机中的j结点，必取串的状态为k时的最优情况。
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 0x11111111
#define maxn 210005
#define eps 1e-8
#define zero(a) fabs(a) #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 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< 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 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];
int pot[2][M][1<<8];
void slove(){
int l=strlen(str);
mem(del[1],0x11);
mem(pot[1],0x8f);
del[1][0][0]=0;
pot[1][0][0]=0;
for(int i=0;i mem(del[i&1],0x11);
mem(pot[i&1],0x8f);
for(int j=0;j for(int k=0;k<(1< if(del[(i+1)&1][j][k]>=inf) continue;
if(del[i&1][j][k]>del[(i+1)&1][j][k]+

HDU 4534 郑厂长系列故事――新闻净化(AC自动机+DP) (一)