hdu 5745 La Vie en rose DP + bitset优化

http://acm.hdu.edu.cn/showproblem.php?pid=5745

这题好劲爆啊。dp容易想，但是要bitset优化，就想不到了。

先放一个tle的dp。复杂度O(n * m)的

第一个串，记作str[]，第二个记作sub[]

思路就是，设dp[i][j][k]表示，匹配了sub的前i个，以str的第j个结尾，然后sub[i]有三种状态，0表示不变化，1表示和前一个，2表示和后一个。

那么以求dp[i][j][0]为列

因为需要的是判断str的第j个结尾是否和sub的前i个完全匹配。

那么，要使得dp[i][j][0]为true，必然需要前i - 1个和j - 1个匹配成功。就是要递推过来。

那么dp[i][j][0] = (dp[i - 1][j - 1][0] || dp[i - 1][j - 1][1]) && (str[j] == sub[i])

其他的类似啦。

可以滚动下数组。

不清0的话，直接用DFN代替即可。这样的复杂度就是O(n * m)，没有常数。但是还是TLE.

#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 = 1e5 + ;

char str[maxn], sub[maxn];

int dp[][maxn][];

int DFN;

char ans[maxn];

void work() {

    DFN++;

    int lenstr, lensub;

    scanf("%d%d", &lenstr, &lensub);

    scanf("%s", str + );

    scanf("%s", sub + );

//    dp[0][0][0] = DFN;

    for (int i = ; i <= lenstr; ++i) dp[][i][] = DFN;

    int now = ;

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

        now = !now;

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

//            if ((dp[i - 1][j - 1][0] || dp[i - 1][j - 1][1]) && str[j] == sub[i]) {

//                dp[i][j][0] = true;

//            }

//            if (dp[i - 1][j - 1][2] && str[j] == sub[i - 1]) {

//                dp[i][j][1] = true;

//            }

//            if ((dp[i - 1][j - 1][0] || dp[i - 1][j - 1][1]) && sub[i + 1] == str[j]) {

//                dp[i][j][2] = true;

//            }

            if ((dp[!now][j - ][] == DFN || dp[!now][j - ][] == DFN) && str[j] == sub[i]) {

                dp[now][j][] = DFN + ;

            }

            if (dp[!now][j - ][] == DFN && str[j] == sub[i - ]) {

                dp[now][j][] = DFN + ;

            }

            if ((dp[!now][j - ][] == DFN || dp[!now][j - ][] == DFN) && str[j] == sub[i + ]) {

                dp[now][j][] = DFN + ;

            }

        }

        DFN++;

    }

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

        ans[i] = '';

        if (dp[now][i][] == DFN || dp[now][i][] == DFN || dp[now][i][] == DFN) {

//            printf("1");

            ans[i - lensub + ] = '';

        }

    }

    ans[lenstr + ] = '\0';

    printf("%s\n", ans + );

}

int main() {

#ifdef local

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

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

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}

然后百度了一个bitset的优化。

考虑用bitset<1e5> dp[5000][k]

dp[i][k]

表示，处理了sub的前i个，当前sub的状态是k，然后匹配整个str串的结果就是dp[i][k]，因为dp[i][k]是一个长度为1e5的01串嘛。也就是dp[i][k]就是匹配好的结果了。

那么，要快速计算dp[i][0]，只需要(dp[i - 1][0] | dp[i - 1][1]) << 1

比如前2个匹配好的结果是"10"和"11"然后匹配成的第三位，就是"011"，关键看看第三位，是1,也就是上面的dp[i - 1][j - 1][k] = true的意思。就是前面的匹配好了，但是还要看看str[j]和sub[i]的相等情况。

要想这一位是true，必然要这一位和sub对应相等。但是我们一次要算出整一个结果，而不是一个一个地算，那么，预处理个pos[26]的bitset就可以，&一下，就是要对应位置是1的，才是true。

3478ms，我是卡过去的

后来一直TLE

#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 = 1e5 + ;

bitset<maxn> dp[][];

char str[maxn], sub[maxn];

bitset<maxn>pos[];

void init() {

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

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

            dp[i][j].reset();

        }

    }

    for (int i = ; i < ; ++i) pos[i].reset();

}

char ans[maxn];

void work() {

    init();

    int lenstr, lensub;

    scanf("%d%d", &lenstr, &lensub);

    scanf("%s%s", str + , sub + );

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

        pos[str[i] - 'a'][i] = ;

    }

    dp[][] = pos[sub[] - 'a'];

    if (lensub >= ) dp[][] = pos[sub[] - 'a'];

    int now = ;

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

        now = !now;

        dp[now][] = ((dp[!now][] | dp[!now][]) << ) & pos[sub[i] - 'a'];

        dp[now][] = (dp[!now][] << ) & pos[sub[i - ] - 'a'];

        if (i < lensub) {

            dp[now][] = ((dp[!now][] | dp[!now][]) << ) & pos[sub[i + ] - 'a'];

        }

    }

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

        if (i + lensub -  > lenstr) {

            ans[i] = '';

        } else {

            if (dp[now][][i + lensub - ] || dp[now][][i + lensub - ]) {

                ans[i] = '';

            } else ans[i] = '';

        }

    }

    ans[lenstr + ] = '\0';

    printf("%s\n", ans + );

//    printf("\n");

}

int main() {

#ifdef local

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

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

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}

巴特西

hdu 5745 La Vie en rose DP + bitset优化

最新文章

热门文章