AC自動機水題，想清楚狀態表示即可。
我一開始多設計一維狀態記錄之前用了多少個刪除操作，MLE，其實這個狀態不需要記錄的，作為一個待求最值的變量。
[cpp]
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 1700
using namespace std;
const int INF=-((~(0U))>>1);
char s[110];
int score;
int next[N][26],pos,flag[N],sta[N],val[N],fail[N],tot;
int newnode(){
memset(next[pos],0,sizeof(next[pos]));
flag[pos]=fail[pos]=sta[pos]=val[pos]=0;
return pos++;
}
void insert(char * s,int score){
int p=0,i;
for(i=0;s[i];i++){
int k=s[i]-'a';
p=next[p][k]?next[p][k]:next[p][k]=newnode();
}
if(score==999){
flag[p]=1;
sta[p]=(1<<tot);
tot++;
}
else if(score==-999){
flag[p]=-1;
}
else{
flag[p]=2;
val[p]=score;
}
}
void makefail(){
queue<int>q;
q.push(0);
int i,p=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(i=0;i<26;i++){
int v=next[u][i];
if(v==0) next[u][i]=next[fail[u]][i];
else q.push(v);
if(u&&v){
fail[v]=next[fail[u]][i];
if(flag[fail[v]]==-1){
flag[v]=-1;
}
else if(flag[v]!=-1){
sta[v]|=sta[fail[v]];
val[v]+=val[fail[v]];
}
}
}
}
}
int dp[2][260][N];
int cost[2][260][N];
void makeans(){
int i,j,k,len,cur;
len=strlen(s);
cur=1;
for(j=0;j<(1<<tot);j++)
for(k=0;k<pos;k++)
dp[0][j][k]=-INF,cost[0][j][k]=INF;
dp[0][0][0]=0;
cost[0][0][0]=0;
for(i=0;s[i];i++){
for(j=0;j<(1<<tot);j++)
for(k=0;k<pos;k++)
dp[cur][j][k]=-INF,cost[cur][j][k]=INF;
for(j=0;j<(1<<tot);j++){
for(k=0;k<pos;k++){
if(dp[cur^1][j][k]==-INF)continue;
if(dp[cur][j][k]>dp[cur^1][j][k]+1){
dp[cur][j][k]=dp[cur^1][j][k]+1;
cost[cur][j][k]=cost[cur^1][j][k];
}
else if(dp[cur][j][k]==dp[cur^1][j][k]+1){
cost[cur][j][k]=max(cost[cur][j][k],cost[cur^1][j][k]);
}
}
}
for(j=0;j<(1<<tot);j++){
for(k=0;k<pos;k++){
if(dp[cur^1][j][k]==-INF)continue;
int v=next[k][s[i]-'a'];
if(flag[v]==-1)continue;
//if((j|sta[v])==((1<<tot)-1)) printf("***%d %d %d %d\n",i,j,k,p);
if(dp[cur][j|sta[v]][v]>dp[cur^1][j][k]){
dp[cur][j|sta[v]][v]=dp[cur^1][j][k];
cost[cur][j|sta[v]][v]=cost[cur^1][j][k]+val[v];
}
else if(dp[cur][j|sta[v]][v]==dp[cur^1][j][k]){
cost[cur][j|sta[v]][v]=max(cost[cur][j|sta[v]][v],cost[cur^1][j][k]+val[v]);
}
}
}
cur^=1;
}
int ans1=-INF;
int ans=INF;
for(j=0;j<pos;j++){
if(dp[cur^1][(1<<tot)-1][j]<ans1){
ans1=dp[cur^1][(1<<tot)-1][j];
ans=cost[cur^1][(1<<tot)-1][j];
}
else if(dp[cur^1][(1<<tot)-1][j]==ans1){
ans=max(ans,cost[cur^1][(1<<tot)-1][j]);
}
}
if(ans1!=-INF){
printf("%d %d\n",ans1,ans);
return ;
}
printf("Banned\n");
}
int main(){
int t,T,n,i,j;
scanf("%d",&T);
for(t=1;t<=T;t++){
scanf("%d",&n);
pos=0,newnode();
tot=0;
for(i=1;i<=n;i++){
scanf("%s %d",s,&score);
insert(s,score);
}
makefail();
scanf("%s",s);
printf("Case %d: ",t);
makeans();
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 1700
using namespace std;
const int INF=-((~(0U))>>1);
char s[110];
int score;
int next[N][26],pos,flag[N],sta[N],val[N],fail[N],tot;
int newnode(){
memset(next[pos],0,sizeof(next[pos]));
flag[pos]=fail[pos]=sta[pos]=val[pos]=0;
return pos++;
}
void insert(char * s,int score){
int p=0,i;
for(i=0;s[i];i++){
int k=s[i]-'a';
p=next[p][k]?next[p][k]:next[p][k]=newnode();
}
if(score==999){
flag[p]=1;
sta[p]=(1<<tot);
tot++;
}
else if(score==-999){
flag[p]=-1;
}
else{
flag[p]=2;
val[p]=score;
}
}
void makefail(){
queue<int>q;
q.push(0);
int i,p=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(i=0;i<26;i++){
int v=next[u][i];
if(v==0) next[u][i]=next[fail[u]][i];
else q.push(v);
if(u&&v){
fail[v]=next[fail[u]][i];
if(flag[fail[v]]==-1){
flag[v]=-1;
}
else if(flag[v]!=-1){
sta[v]|=sta[fail[v]];
val[v]+=val[fail[v]];
}
}
}
}
}
int dp[2][260][N];
int cost[2][260][N];
void makeans(){
int i,j,k,len,cur;
len=strlen(s);
cur=1;
for(j=0;j<(1<<tot);j++)
for(k=0;k<pos;k++)
dp[0][j][k]=-INF,cost[0][j][k]=INF;
dp[0][0][0]=0;
cost[0][0][0]=0;
for(i=0;s[i];i++){
for(j=0;j<(1<<tot);j++)
for(k=0;k<pos;k++)
dp[cur][j][k]=-INF,cost[cur][j][k]=INF;
for(j=0;j<(1<<tot);j++){
for(k=0;k<pos;k++){
if(dp[cur^1][j][k]==-INF)continue;
if(dp[cur][j][k]>dp[cur^1][j][k]+1){
dp[cur][j][k]=dp[cur^1][j][k]+1;
cost[cur][j][k]=cost[cur^1][j][k];
}
else if(dp[cur][j][k]==dp[cur^1][j][k]+1){
cost[cur][j][k]=max(cost[cur][j][k],cost[cur^1][j][k]);
}
}
}
for(j=0;j<(1<<tot);j++){
for(k=0;k<pos;k++){
if(dp[cur^1][j][k]==-INF)continue;
int v=next[k][s[i]-'a'];
if(flag[v]==-1)continue;
//if((j|sta[v])==((1<<tot)-1)) printf("***%d %d %d %d\n",i,j,k,p);
if(dp[cur][j|sta[v]][v]>dp[cur^1][j][k]){
dp[cur][j|sta[v]][v]=dp[cur^1][j][k];
cost[cur][j|sta[v]][v]=cost[cur^1][j][k]+val[v];
}
else if(dp[cur][j|sta[v]][v]==dp[cur^1][j][k]){
cost[cur][j|sta[v]][v]=max(cost[cur][j|sta[v]][v],cost[cur^1][j][k]+val[v]);
}
}
}
cur^=1;
}
int ans1=-INF;
int ans=INF;
for(j=0;j<pos;j++){
if(dp[cur^1][(1<<tot)-1][j]<ans1){
ans1=dp[cur^1][(1<<tot)-1][j];
ans=cost[cur^1][(1<<tot)-1][j];
}
else if(dp[cur^1][(1<<tot)-1][j]==ans1){
ans=max(ans,cost[cur^1][(1<<tot)-1][j]);
}
}
if(ans1!=-INF){
printf("%d %d\n",ans1,ans);
return ;
}
printf("Banned\n");
}
int main(){
int t,T,n,i,j;
scanf("%d",&T);
for(t=1;t<=T;t++){
scanf("%d",&n);
pos=0,newnode();
tot=0;
for(i=1;i<=n;i++){
scanf("%s %d",s,&score);
insert(s,score);
}
makefail();
scanf("%s",s);
printf("Case %d: ",t);
makeans();
}
return 0;
}
