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

模板。。

差不多的题目:
HDU 1423
ZOJ 2432

/*94ms,2152KB*/

const int mx = 505;

int a[mx], b[mx];
int dp[mx][mx], pre[mx][mx], ans[mx];

int get_lcis(int n, int m) /// 注意a,b数组要从1开始读
{
    int i, j, k;
    Forr(i, 1, n + 1)
    {
        k = 0;
        Forr(j, 1, m + 1)
        {
            if (a[i] != b[j]) dp[i][j] = dp[i - 1][j];
            if (a[i] > b[j] && dp[i][j] > dp[i][k]) k = j;
            if (a[i] == b[j]) dp[i][j] = dp[i][k] + 1, pre[i][j] = k;
        }
    }
    int maxlen = -1, x = n, y = 0;
    Forr(i, 1, m + 1) if (dp[n][i] > maxlen) maxlen = dp[n][i], y = i;
    int cnt = 1;
    while (dp[x][y])
    {
        if (a[x] != b[y]) --x;
        else ans[maxlen - cnt] = b[y], ++cnt, y = pre[x][y];
    }
    return maxlen;
}

int main()
{
    int n, m, i, maxlen;
    SI(n);
    SA(a + 1, i, n);
    SI(m);
    SA(b + 1, i, m);
    PI(maxlen = get_lcis(n, m));
    PA(ans, i, maxlen);
    return 0;
}

Comments

comments powered by Disqus