C. Dasha and Password 预处理＋　dp

http://codeforces.com/contest/761/problem/C

对于每一个字符串，可以预处理出其到达数字，字母，和特殊符号所需的最小步数。

然后就是在n个东西中，选出数字、字母和特殊符号，至少一个，所需的最少步数。

因为第一个选了数字的话，它就不能选字母的了，然后比赛的时候发现这就是二分图，然后就上了km的模板。（太笨了我）

虽然过了，但是明显正解不是这个。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn =  + ;

char str[maxn][maxn];

int e[ + ][ + ];

int match[maxn];//match[col] = row

int vx[maxn], vy[maxn];

int fx[maxn], fy[maxn];

int dfs (int u, int m) {

    vx[u] = ;

    int i;

    for (i = ; i <= m; i++) { //筛选n个 导航员 col的值

        if (vy[i] ==  && fx[u] + fy[i] == e[u][i]) {

            vy[i] = ;

            if (match[i] ==  || dfs(match[i], m)) {

                match[i] = u; // match[col]=row;

                return ;//搭配成功

            }

        }

    }

    return ;//我找不到啊，后面，就会执行km

}

void do_km(int n, int m) { //

    int i, j;

    int d = -inf;

    for (i = ; i <= n; i++) { //遍历每一个驾驶员 row的值

        if (vx[i] == ) {

            for (j = ; j <= m; j++) { //对他进行遍历导航员 col的值

                if (!vy[j]) {

                    if (d < (fx[i] + fy[j] - e[i][j])) {

                        d = fx[i] + fy[j] - e[i][j];

                    }

                }

            }

        }

    }

    for (i = ; i <= n; i++) {

        if (vx[i] == ) {

            fx[i] -= d;

            vx[i] = ; //请0

        }

        if (vy[i] == ) { //

            fy[i] += d;

            vy[i] = ; //情0

        }

    }

    return ;

}

int anskm(int n, int m) {

    memset(vx, , sizeof(vx));

    memset(vy, , sizeof(vy));

    memset(fx, , sizeof(fx));

    memset(fy, , sizeof(fy));

    memset(match, , sizeof(match));

    //km算法的一部分，先初始化fx，fy

    for (int i = ; i <= n; i++) { //遍历每一个驾驶员 row的值

        fy[i] = ;

        fx[i] = inf; //无穷小

        for (int j = ; j <= m; j++) { //遍历每一个导航员 col的值

            if (fx[i] > e[i][j]) { //默契值

                fx[i] = e[i][j];

            }

        }

    }

    for (int i = ; i <= n; i++) { //遍历每一个驾驶员 row的值

        memset(vx, , sizeof(vx));

        memset(vy, , sizeof(vy));

        while (!dfs(i, m)) {//如果他找不到搭配，就实现km算法

            do_km(n, m);//km完后，还是会对这个想插入的节点进行dfs的,因为他还没搭配嘛

        }

    }

    int ans = ;

    for (int i = ; i <= m; i++) //遍历导航员，col的值

        ans += e[match[i]][i];//输入的row是驾驶员，col是导航员

    //match[i]:导航员i和驾驶员match[i]搭配了              match[col]=row;

    return ans;

}

void work() {

    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = ; i <= ; ++i) {

        for (int j = ; j <= ; ++j) {

            e[i][j] = ;

        }

    }

    for (int i = ; i <= n; ++i) {

        scanf("%s", str[i] + );

        int a = , b = , c = ;

        int len = m;

        for (int j = ; str[i][j]; ++j) {

            if (str[i][j] >= '' && str[i][j] <= '') {

                a = min(a, j - );

            } else if (str[i][j] == '#' || str[i][j] == '*' || str[i][j] == '&') {

                b = min(b, j - );

            } else {

                c = min(c, j - );

            }

        }

        for (int j = len; j >= ; j--) {

            if (str[i][j] >= '' && str[i][j] <= '') {

                a = min(a, len - j + );

            } else if (str[i][j] == '#' || str[i][j] == '*' || str[i][j] == '&') {

                b = min(b, len - j + );

            } else {

                c = min(c, len - j + );

            }

        }

        e[i][] = a;

        e[i][] = b;

        e[i][] = c;

    }

//    for (int i = 1; i <= n; ++i) {

//        for (int j = 1; j <= n; ++j) {

//            cout << e[i][j] << " ";

//        }

//        cout << endl;

//    }

    cout << anskm(n, n) - (n - ) *  << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

正解因该是一个dp

dp[i][2][2]][2]表示在前i个字符串中，选出了数字（0 or 1）、字母、特殊符号所需的最小步数。

转移

dp[now][a][b][c] = min(dp[now][a][b][c], dp[!now][a][b][c]); //保留上次的最小值。

然后对于每一个a、b、c

dp[now][a][b][c] = min(dp[now][a][b][c], dp[!now][a - 1][b][c] + e[i][1]);之类的。

一开始还担心会不会使得同一个字符串，既选了数字，也选了字母。

然后是不会的，因为需要选数字的时候，是从dp[!now][a - 1][b][c]转移过来的，也就是从上一唯的b、c转过来。所以不会有重复。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn =  + ;

char str[maxn][maxn];

int e[ + ][ + ];

int dp[][][][];

void work() {

    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = ; i <= ; ++i) {

        for (int j = ; j <= ; ++j) {

            e[i][j] = ;

        }

    }

    for (int i = ; i <= n; ++i) {

        scanf("%s", str[i] + );

        int a = , b = , c = ;

        int len = m;

        for (int j = ; str[i][j]; ++j) {

            if (str[i][j] >= '' && str[i][j] <= '') {

                a = min(a, j - );

            } else if (str[i][j] == '#' || str[i][j] == '*' || str[i][j] == '&') {

                b = min(b, j - );

            } else {

                c = min(c, j - );

            }

        }

        for (int j = len; j >= ; j--) {

            if (str[i][j] >= '' && str[i][j] <= '') {

                a = min(a, len - j + );

            } else if (str[i][j] == '#' || str[i][j] == '*' || str[i][j] == '&') {

                b = min(b, len - j + );

            } else {

                c = min(c, len - j + );

            }

        }

        e[i][] = a;

        e[i][] = b;

        e[i][] = c;

    }

    memset(dp, 0x3f, sizeof dp);

    int now = ;

    dp[now][][][] = ;

    for (int i = ; i <= n; ++i) {

        now = !now;

        for (int a = ; a <= ; ++a) {

            for (int b = ; b <= ; ++b) {

                for (int c = ; c <= ; ++c) {

                    dp[now][a][b][c] = min(dp[now][a][b][c], dp[!now][a][b][c]);

                    if (a) {

                        dp[now][a][b][c] = min(dp[now][a][b][c], dp[!now][a - ][b][c] + e[i][]);

//                        break;

                    }

                    if (b) {

                        dp[now][a][b][c] = min(dp[now][a][b][c], dp[!now][a][b - ][c] + e[i][]);

//                        break;

                    }

                    if (c) {

                        dp[now][a][b][c] = min(dp[now][a][b][c], dp[!now][a][b][c - ] + e[i][]);

//                        break;

                    }

                }

            }

        }

    }

    cout << dp[now][][][] << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

巴特西

C. Dasha and Password 预处理＋　dp

最新文章

热门文章

巴特西

C. Dasha and Password 预处理 ＋ dp

最新文章

热门文章

C. Dasha and Password 预处理＋　dp