POJ 1692 Crossed Matchings dp[][] 比较有意思的dp

http://poj.org/problem?id=1692

这题看完题后就觉得我肯定不会的了，但是题解却很好理解。- - ，做题阴影吗

所以我还是需要多思考。

题目是给定两个数组，要求找出最大匹配数量。

匹配规则是：

a[i] ==b[j]，而且需要产生交叉，而且没对数只能匹配一次。

一开始的时候我被交叉吓到了，怎么判断交叉啊？

分析：

对于a[]的第i个数，b数组的第j个数，假设a[i] != b[j] 如果它能产生匹配，那么就需要，

对于a[i]这个数字，在b[]的前j - 1个找到和他数字相等的，

对于b[j]这个数字，在a[]的前i - 1个数中找到一个数字，和b[j]相等，

这个时候，他们不仅能匹配，而且还是合法了，就是交叉了。所以在这个状态转移过来就好。

所以设dp[i][j]表示a[]的前i个数，b[]的前j个数。能匹配的最大数量。

dp[i][j] = max(dp[i][j], dp[posa - 1][posb - 1] + 2);

当然，第i个数和第j个数也可以不用来匹配，但是要把答案传递下去，所以开始的时候。

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

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

int dp[maxn][maxn];

int a[maxn], b[maxn];

int toFindPos(int nowPos, int val, int which) {

    if (which == ) {

        while (nowPos--) {

            if (nowPos == ) return inf;

            if (a[nowPos] == val) return nowPos;

        }

    } else {

        while(nowPos--) {

            if (nowPos == ) return inf;

            if (b[nowPos] == val) return nowPos;

        }

    }

    assert(false);

}

void work() {

    int lena, lenb;

    cin >> lena >> lenb;

    for (int i = ; i <= lena; ++i) cin >> a[i];

    for (int i = ; i <= lenb; ++i) cin >> b[i];

    memset(dp, , sizeof dp);

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

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

            dp[i][j] = max(dp[i - ][j], dp[i][j - ]);

            if (a[i] == b[j]) continue;

            int posA = toFindPos(i, b[j], );

            int posB = toFindPos(j, a[i], );

            if (posA == inf || posB == inf) continue;

            dp[i][j] = max(dp[i][j], dp[posA - ][posB - ] + );

        }

    }

    cout << dp[lena][lenb] << endl;

}

int main() {

#ifdef local

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

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

#endif

    int t;

    cin >> t;

    while (t--) work();

    return ;

}

巴特西

POJ 1692 Crossed Matchings dp[][] 比较有意思的dp

最新文章

热门文章