首页 > ACM题库 > HDU-杭电 > HDU 4534-郑厂长系列故事――新闻净化-动态规划-[解题报告]HOJ
2015
07-17

HDU 4534-郑厂长系列故事――新闻净化-动态规划-[解题报告]HOJ

郑厂长系列故事――新闻净化

问题描述 :

  郑厂长不是正厂长
  也不是副厂长
  他根本就不是厂长
  他曾经是腾讯公司的码农
  一个业余时间喜欢下棋的码农
  但现在
  他神秘失踪了……

  众所周知,在太平洋某岛国,新闻审查是很严格的,而郑厂长的失踪就与该国的新闻审查有关。别担心,他不是喝茶去,而且被秘密邀请承担该国净化新闻的工作了。

  这份工作的主要内容是这样的,对于一篇即将发表的新闻稿,郑厂长需要对它做最后的订正工作:只通过删除一些字母,使其符合“相关要求”。这些要求有,一些词语必须作为子串出现,一些词语必须不能作为子串出现,另一些词语作为子串出现有相应的分数加成,需要注意的是,这个加成分数可能是负的。

  郑厂长要删除最少字母使文章符合要求,并让加成分之和尽可能高。如果一个带有加成分的单词出现了多次,结果也计算多次。

输入:

输入第一行为T,表示有T组测试数据。
每组数据一个N开始,表示有N个在“相关要求”中的单词。为了简化输入,给每个单词都指定一个加成分,加成分为999的,表示“必须作为子串出现”的,加成分为-999的,表示“必须不能作为子串出现”的。
接下来的N行里,每行有一个单词Si和其对应的加成分Gi。最后一行是原稿内容S_ori。

[Technical Specification]

1. 1 <= T <= 47
2. 1 <= N <= 100
3. -999 <= Gi <= 999
4. Gi 为999的单词数目不大于8
5. Gi 为-999的单词数目不大于8
6. 1 <= |Si| <= 16, 1 <= |S_ori| <= 100, |S| 表示字符串S的长度
7. Si 与 S_ori 只由小写字母 ‘a’-‘z’ 组成,不会出现相同的

输出:

输入第一行为T,表示有T组测试数据。
每组数据一个N开始,表示有N个在“相关要求”中的单词。为了简化输入,给每个单词都指定一个加成分,加成分为999的,表示“必须作为子串出现”的,加成分为-999的,表示“必须不能作为子串出现”的。
接下来的N行里,每行有一个单词Si和其对应的加成分Gi。最后一行是原稿内容S_ori。

[Technical Specification]

1. 1 <= T <= 47
2. 1 <= N <= 100
3. -999 <= Gi <= 999
4. Gi 为999的单词数目不大于8
5. Gi 为-999的单词数目不大于8
6. 1 <= |Si| <= 16, 1 <= |S_ori| <= 100, |S| 表示字符串S的长度
7. Si 与 S_ori 只由小写字母 ‘a’-‘z’ 组成,不会出现相同的

样例输入:

3
2
he 999
sh -999
she
2
she 999
he -999
shelovesyou
4
ab 999
cd -999
abd 1
abc -1
abcdefg

样例输出:

Case 1: 1 0
Case 2: Banned
Case 3: 1 1

Hint
对于第三组样例,”abdefg” 和 ”abcefg” 都符合要求,但前者的加成分比后者高。

转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents   
by—cxlove

题目:给出一些模式串,其中有一些串必须出现在子串当中,有一些串是不可以出现在子串中。然后还有一些串有一些分值。给出母串,问最少需要删除多少个字母,能够满足条件,然后使得分值尽可能大。
妥妥的AC自动机+DP啊。
复赛第一场,妥妥的上来做了签到题之后就开始开E题了,然后就没有然后了。。。
AC自动机都能写错,妥妥地WA了几十次啊
每次建fail的时候,都要把val,canot,must进行转移啊,我SB了只转移了val
del[i][j][k],pot[i][j][k]表示前i个字符,当前在自动机中的j结点,必取串的状态为k时的最优情况。
#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];
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<l;i++){
        mem(del[i&1],0x11);
        mem(pot[i&1],0x8f);
        for(int j=0;j<idx;j++){
            for(int k=0;k<(1<<tot);k++){
                if(del[(i+1)&1][j][k]>=inf) continue;
                if(del[i&1][j][k]>del[(i+1)&1][j][k]+1){
                    del[i&1][j][k]=del[(i+1)&1][j][k]+1;
                    pot[i&1][j][k]=pot[(i+1)&1][j][k];
                }
                else if(del[i&1][j][k]==del[(i+1)&1][j][k]+1&&pot[i&1][j][k]<pot[(i+1)&1][j][k]){
                    del[i&1][j][k]=del[(i+1)&1][j][k]+1;
                    pot[i&1][j][k]=pot[(i+1)&1][j][k];
                }
                int id=str[i]-'a';
                if(s[j].next[id]==NULL) continue;
                int cur=s[j].next[id]->kind;
                if(s[cur].canot) continue;
                int val=s[cur].val;
                int curk=k|s[cur].must; 
                if(del[i&1][cur][curk]>del[(i+1)&1][j][k]){
                    del[i&1][cur][curk]=del[(i+1)&1][j][k];
                    pot[i&1][cur][curk]=pot[(i+1)&1][j][k]+val;
                }
                else if(del[i&1][cur][curk]==del[(i+1)&1][j][k] && pot[i&1][cur][curk]<pot[(i+1)&1][j][k]+val){
                    del[i&1][cur][curk]=del[(i+1)&1][j][k];
                    pot[i&1][cur][curk]=pot[(i+1)&1][j][k]+val;
                }
            }
        }
    }
    int a1=inf,a2;
    int full=(1<<tot)-1,num=(l+1)&1;
    for(int i=0;i<idx;i++){
        if(del[num][i][full]<a1){
            a1=del[num][i][full];
            a2=pot[num][i][full];
        }
        else if(del[num][i][full]==a1&&pot[num][i][full]>a2){
            a1=del[num][i][full];
            a2=pot[num][i][full];
        }
    }
    if(a1>=inf) puts("Banned");
    else printf("%d %d\n",a1,a2);
}
int n,val;
int main(){
    // freopen("input.txt","r",stdin);
    int t,cas=0;
    scanf("%d",&t);
    while(t--){
        idx=0;tot=0;
        scanf("%d",&n);
        Trie *root=NewNode();
        for(int i=0;i<n;i++){
            scanf("%s%d",str,&val);
            Insert(root,str,strlen(str),i,val);
        }
        Bulid_fail(root);
        scanf("%s",str);
        printf("Case %d: ",++cas);
        slove();
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/8739294