HDU5791-－Two （DP）

题意：两个数列a,b，求相同的子序列有多少对，内容相同位置不同也算不同。

题解：dp[i][j]表示a数列前i个数个 b数列前j个数 有多少对

递推方程： dp[i][j] = dp[i-1][j-1]( a[i]和b[j]都不用 ) + ∑(k<i&&a[k]==b[j])dp[k-1][j-1] + ∑(k<=j&&a[i]==b[k])dp[i-1][k-1];

for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                dp[i][j] = 0;
                for (int k = 1; k < i; ++k)
                    if (a[k] == b[j]) dp[i][j] = (dp[i][j] + dp[k-1][j-1]) % MOD;
                for (int k = 1; k <= j; ++k)
                    if (a[i] == b[k]) dp[i][j] = (dp[i][j] + dp[i-1][k-1]) % MOD;
                dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD;

            }
}

O(n^3)会超时，所以在每一步多求一些辅助值，可以优化到O(n^2)。

我知道这种做法没问题，但是比赛的时候打死都调不出来，最后还是队友做的，心烦。

突然想到我的做法貌似很蠢……哎 不管了。。。反正过了。。。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#define CLR(x, r) memset(x, r, sizeof (x))
#define PF(x) printf("debug:%d
", x)

using namespace std;
typedef long long ll;

const int N = 1005;
const ll MOD = 1000000007;
int a[N], b[N];
ll dp[N][N];
ll ax[N];
ll bx[N];

int main(int argc, char const *argv[])
{
    freopen("in", "r", stdin);
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= n; ++i) scanf("%d", a+i);
        for (int i = 1; i <= m; ++i) scanf("%d", b+i);
        
        for (int i = 0; i <= n; ++i) dp[i][0] = 1;
        for (int i = 0; i <= m; ++i) dp[0][i] = 1;
        CLR(ax, 0);
        for (int j = 1; j <= m; ++j) {
            if (b[j] == a[1]) bx[j] = bx[j-1] + dp[0][j-1];
            else bx[j] = bx[j-1];
        }
        for (int i = 1; i <= n; ++i) {
            int ant = a[i+1];
            for (int j = 1; j <= m; ++j) {
                dp[i][j] = 0;

                dp[i][j] = (dp[i][j] + ax[j]) % MOD;    // 用到 b[j]
                dp[i][j] = (dp[i][j] + bx[j]) % MOD;    // 用到 a[i]
                dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD;

                if (b[j] == ant) {
                    bx[j] = (bx[j-1] + dp[i][j-1]) % MOD;
                } else {
                    bx[j] = bx[j-1];
                }

                if (b[j] == a[i]) {
                    ax[j] = (ax[j] + dp[i-1][j-1]) % MOD;
                }

            }
        }

        cout << (dp[n][m] - 1 + MOD) % MOD << endl;
    }
    return 0;
}