题意：中文的题目，意思就是说有很多串，每个串都有权值，权值为999的串必须出现，-999的串必须不出现。权值在-999~999之间。
然后必须出现的串不超过8个。然后给一个全为小写目标串，问最少需要删除多少个字母才能够保证必须出现的串都出现，次数一样保证权值最大。输出次数和权值。
然后根据样例，那些必须出现的串，其实权值是0。
思路：
很明显一开始建自动机构成trie图，但是需要注意的就是mark和sum的更新。个人是把所有中间的节点的sum全部赋值成了-inf。
接着只有8个必须出现的串，所以必须要状压一下。
所以最后就是dp[i][j][k][l]，处理了i个字母，在j这个节点，k这个状态。l=0代表这个字母不删，l=1代表这个字母删。
然后是个结构体存两个值次数和评分。然后就是更新的时候有点麻烦。
然后注意一下，最后的评分有可能是负数。
#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
#include"map"
#include"string"
#define inf 999999
using namespace std;
struct trie
{
int mark,id,sum;
trie *next[27],*fail;
trie()
{
mark=0;
sum=-inf;
memset(next,0,sizeof(next));
fail=NULL;
}
};
trie *root,*node[1700];
int triecont;
void init(char *v,int k,int x)
{
trie *p=root;
for(int i=0; v[i]; i++)
{
int tep=v[i]-'a';
if(p->next[tep]==NULL)
{
p->next[tep]=new trie();
p->next[tep]->id=triecont;
node[triecont++]=p->next[tep];
}
p=p->next[tep];
}
if(k==1) //必须出现
{
p->mark=(1<
sum=0;
}
else if(k==-1) p->mark=-1; //必须不出现
else p->sum=x; //无特定要求
}
void getac()
{
queue
q; q.push(root); while(!q.empty()) { trie *p=q.front(); q.pop(); for(int i=0; i<26; i++) { if(p->next[i]==NULL) { if(p==root) p->next[i]=root; else p->next[i]=p->fail->next[i]; } else { if(p==root) p->next[i]->fail=root; else p->next[i]->fail=p->fail->next[i]; q.push(p->next[i]); if(p!=root) { if(p->next[i]->mark==-1 || p->next[i]->fail->mark==-1) //更新必须不出现 p->next[i]->mark=-1; else { p->next[i]->mark|=p->next[i]->fail->mark; if(p->next[i]->fail->sum!=-inf) //更新权值 { if(p->next[i]->sum==-inf) p->next[i]->sum=0; p->next[i]->sum+=p->next[i]->fail->sum; } } } } } } } struct Dp { int cs,pf; } dp[2][1605][259][2]; //这里必须要滚动，不然MLE int main() { int t,cas=1; cin>>t; while(t--) { triecont=0; root=new trie(); node[triecont]=root; root->id=triecont++; int n,cnt=0; scanf("%d",&n); while(n--) { char x[177]; int y; scanf("%s%d",x,&y); if(y==-999) init(x,-1,0); else if(y==999) init(x,1,cnt++); else init(x,0,y); } getac(); char fuck[123]; scanf("%s",fuck); int len=strlen(fuck); for(int i=0; i
next[fuck[i-1]-'a']->mark!=-1) //这里需要注意，有的情况是必须删除的，所以不删除的情况是要判断一下的。 { trie *p=node[j]->next[fuck[i-1]-'a']; int tep=p->mark|k; Dp cur=dp[i%2][p->id][tep][0],now; if(dp[1-i%2][j][k][0].cs
dp[1-i%2][j][k][1].cs) now=dp[1-i%2][j][k][1]; else { now.cs=dp[1-i%2][j][k][1].cs; now.pf=max(dp[1-i%2][j][k][0].pf,dp[1-i%2][j][k][1].pf); } if(p->sum!=-inf) { if(now.pf==inf) now.pf=0; now.pf+=p->sum; } if(now.cs
id][tep][0]=cur; } Dp cur=dp[i%2][j][k][1],now; //这里是这个位置删除的更新 if(dp[1-i%2][j][k][0].cs
dp[1-i%2][j][k][1].cs) now=dp[1-i%2][j][k][1]; else { now.cs=dp[1-i%2][j][k][1].cs; now.pf=max(dp[1-i%2][j][k][0].pf,dp[1-i%2][j][k][1].pf); } now.cs++; if(now.cs