「6月雅礼集训 2017 Day1」说无可说

【题目大意】

给出n个字符串，求有多少组字符串之间编辑距离为1~8。

n<=200，∑|S| <= 10^6

【题解】

首先找编辑距离有一个n^2的dp，由于发现只找小于等于8的，所以搜旁边16个状态即可。

复杂度O(n^2|S| * 16)

# include <vector>
# include <stdio.h>
# include <iostream>
# include <string.h>
# include <algorithm>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int N = 200 + 10, M = 1e6 + 10, AN = 10;
const int mod = 1e9 + 7;

int n, len[M], ans[AN];
vector<char> a[N];
char str[M];

int u, v;
int dp[2][M];
inline int f(int i, int j) {
    if(i == 0) return j;
    if(j == 0) return i;
    if(j < max(1, i-8) || j > min(len[v], i+8)) return 1e9;
    return dp[i&1][j];
}

inline void fin(int i, int j, int s) {
    dp[i&1][j] = s;
}

inline int gans() {
    for (int i=1; i<=len[v] || i<=len[u]; ++i) fin(0, i, 0), fin(1, i, 0);
    for (int i=1; i<=len[u]; ++i)
        for (int j=max(1, i-8), jto = min(i+8, len[v]); j<=jto; ++j) {
            fin(i, j, min(f(i-1, j), f(i, j-1)) + 1);
            if(a[u][i-1] != a[v][j-1]) fin(i, j, min(f(i, j), f(i-1, j-1) + 1));
            else fin(i, j, min(f(i, j), f(i-1, j-1)));
        }
    return f(len[u], len[v]);
}

int main() {
//    freopen("say.in", "r", stdin);
//    freopen("say.out", "w", stdout);
    cin >> n;
    for (int i=1; i<=n; ++i) {
        scanf("%s", str);
        len[i] = strlen(str);
        for (int j=0; str[j]; ++j) a[i].push_back(str[j]);
    }
    for (int i=1, tem; i<=n; ++i) {
        for (int j=i+1; j<=n; ++j) {
            u = i, v = j;
            tem = gans(); 
            if(tem >= 1 && tem <= 8) ++ ans[tem];
        }
    }
    
    for (int i=1; i<=8; ++i) cout << ans[i] << ' ';
    cout << endl;
    return 0;
}

当然，过不了，有60分。

所以考虑dp有很多空余状态，改成dfs加剪枝就可以过了。。

# include <vector>
# include <stdio.h>
# include <iostream>
# include <string.h>
# include <algorithm>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int N = 200 + 10, M = 1e6 + 10, AN = 10;
const int mod = 1e9 + 7;

int n, len[M], ans[AN];
vector<char> a[N];
char str[M];

# define ABS(x) ((x) > 0 ? (x) : -(x))

int tem;
inline void solve(int u, int v, int cur_u, int cur_v, int cnt) {
    if(cnt + ABS(len[v] - len[u] - (cur_v - cur_u)) >= tem) return;
    while(cur_u < len[u] && cur_v < len[v]) {
        if(a[u][cur_u] != a[v][cur_v]) {
            solve(u, v, cur_u+1, cur_v, cnt+1);
            solve(u, v, cur_u, cur_v+1, cnt+1);
            solve(u, v, cur_u+1, cur_v+1, cnt+1);
            return ;
        }
        ++cur_u, ++cur_v;
    }
    if(cur_u == len[u]) tem = min(tem, cnt + len[v] - cur_v);
    if(cur_v == len[v]) tem = min(tem, cnt + len[u] - cur_u);
}

int main() {
//    freopen("say.in", "r", stdin);
//    freopen("say.out", "w", stdout);
    cin >> n;
    for (int i=1; i<=n; ++i) {
        scanf("%s", str);
        len[i] = strlen(str);
        for (int j=0; str[j]; ++j) a[i].push_back(str[j]);
    }
    for (int i=1; i<=n; ++i) {
        for (int j=i+1; j<=n; ++j) {
            tem = 9;
            solve(i, j, 0, 0, 0);
            ++ ans[tem];
        }
    }
    
    for (int i=1; i<=8; ++i) cout << ans[i] << ' ';
    cout << endl;
    
    return 0;
}

这里dfs的时候需要注意一点，要一段一段跳，不能一格一格跳，会T。。