HDU - 2457 DNA repair AC自动机+dp - ProLightsfx的技术成长

D - DNA repair AC自动机+dp

Source

HDU 2457

My Solution

题意：给出n个模式串，给出一个主串，要求在主创上改动尽可能少的字符，使任一模式串不在主串中出现。

AC自动机+dp

按照一般的 AC自动机+dp转移的模式(套路)来做，与1月底做的一个经典例题题差不多
URAL - 1158 Censored! AC自动机+dp

http://blog.csdn.net/prolightsfxjh/article/details/54729646

定义dpij表示主串上si字符自动机上的j节点时的最少方案。

如果自动机上j节点的下一个节点ac.ch[j][k]; 0 <= k < 4

如果是危险节点则continue;

如果刚好是s[i]，则不用改即 dp[i+1][ac.ch[j][k] = min(dp[i+1][ac.ch[j][k], dp[i][j])；

如果不是则要改即 dp[i+1][ac.ch[j][k] = min(dp[i+1][ac.ch[j][k], dp[i][j] + 1)；

答案就是 dp[szs][j]的最小值。

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef long long LL;
const int INF = 1e9 + 8;
const int CHAR_SIZE = 4;
const int MAX_SIZE = 1e3 + 8;
map<char, int> mp;

struct AC_Machine{
    int ch[MAX_SIZE][CHAR_SIZE], danger[MAX_SIZE], fail[MAX_SIZE];
    int sz;

    inline void init(){
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        memset(danger, 0, sizeof danger);
    }

    inline void _insert(const string &s){
        int n = s.size();
        int u = 0, c;
        for(int i = 0; i < n; i++){
            c = mp[s[i]];
            if(!ch[u][c]){
                memset(ch[sz], 0, sizeof ch[sz]);
                danger[sz] = 0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        danger[u]++;
    }

    inline void _build(){
        queue Q;
        fail[0] = 0;
        for(int c = 0, u; c < CHAR_SIZE; c++){
            u = ch[0][c];
            if(u){Q.push(u); fail[u] = 0;}
        }
        int r;
        while(!Q.empty()){
            r = Q.front();
            Q.pop();
            danger[r] |= danger[fail[r]];
            for(int c = 0, u; c < CHAR_SIZE; c++){ u = ch[r][c]; if(!u){ch[r][c] = ch[fail[r]][c]; continue; } fail[u] = ch[fail[r]][c]; Q.push(u); } } } }ac; string s; int dp[MAX_SIZE][MAX_SIZE]; int main() { #ifdef LOCAL freopen("d.txt", "r", stdin); //freopen("d.out", "w", stdout); #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int n, szs,i, j, k, ans, kase = 1; mp['A'] = 0, mp['G'] = 1, mp['C'] = 2, mp['T'] = 3; while(true){ cin >> n;
        if(n == 0) break;
        ac.init();
        for(i = 0; i < n; i++){ cin >> s;
            ac._insert(s);
        }
        ac._build(); cin >> s; szs = s.size();
        for(i = 0; i <= szs; i++){
            for(j = 0; j < ac.sz; j++){
                dp[i][j] = INF;
            }
        }
        dp[0][0] = 0; ans = INF;
        for(i = 0; i < szs; i++){
            for(j = 0; j < ac.sz; j++){
                if(dp[i][j] == INF) continue;
                for(k = 0; k < CHAR_SIZE; k++){
                    //cout << j << " " << k << " : " << ac.danger[ac.ch[j][k]] << endl;
                    if(ac.danger[ac.ch[j][k]]) continue;
                    dp[i+1][ac.ch[j][k]] = min(dp[i+1][ac.ch[j][k]], dp[i][j] + (k != mp[s[i]]));
                }
            }
        }
        for(j = 0; j < ac.sz; j++) ans = min(ans, dp[szs][j]);
        if(ans == INF) cout << "Case " << kase << ": -1" << "n";
        else cout << "Case " << kase << ": " << ans << "n";
        kase++;
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

HDU – 2457 DNA repair AC自动机+dp

D - DNA repair AC自动机+dp

相关推荐

HDU – 5769 Substring 后缀自动机+二分、新增distinct子串的个数和位置

HDU – 2825 Wireless Password AC自动机+状压dp

HihoCoder – 1449 后缀自动机三·重复旋律6 后缀自动机、递推、DFS

Gym – 101164C Castle KMP的拓展、next数组+dp、好题

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类