Codeforces 10D LCIS 找出最长公共子和产量增加这个序列 dp

主题链接：点击打开链接

意甲冠军：

特定n长序列

给定k长序列

求LCIS并输出这个子序列

如有多解输出随意解。。

= - = 敲的时候听着小曲儿pre的含义还没有想清楚，万万没想到就过了。。。

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<set>

#include<vector>

#include<map>

#include<math.h>

#include<string>

#include<stdlib.h>

#include<algorithm>

using namespace std;

#define N 505

int a[N],s[N];

int n, k;

int dp[N][N];

int pre[N][N][2];

int is[N][N];

vector<int>G;

int main(){

	int i,j,co;

	while(~scanf("%d",&n)){

		G.clear();

		for(i=1;i<=n;i++)scanf("%d",&a[i]);

		scanf("%d",&k);

		for(i=1;i<=k;i++)scanf("%d",&s[i]);

		memset(dp, 0, sizeof dp);

		memset(pre, 0, sizeof pre);

		memset(is, 0, sizeof is);

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

			int maxx = 0;

			int x = 0, y = 0;

			for(j=1;j<=k;j++)

			{

				dp[i][j] = dp[i-1][j];

				if(a[i]>s[j] && maxx < dp[i-1][j]) {

					maxx = dp[i-1][j];

					if(is[i-1][j])

						x = i-1, y = j;

					else {

						x = pre[i-1][j][0];

						y = pre[i-1][j][1];

					}

				}

				if(a[i]==s[j]) {

					is[i][j] = 1;

					dp[i][j] = maxx + 1;

					if(is[x][y])

						pre[i][j][0] = x, pre[i][j][1] = y;

					else {

						pre[i][j][0] = pre[x][y][0];

						pre[i][j][1] = pre[x][y][1];

					}

					continue;

				}

				if(is[i-1][j])

					pre[i][j][0] = i-1, pre[i][j][1] = j;

				else {

					pre[i][j][0] = pre[i-1][j][0];

					pre[i][j][1] = pre[i-1][j][1];

				}

			}

		}

		int ans = 0;

		int x = n, y = k;

		for(i=1;i<=k;i++)if(ans<dp[n][i]){

			ans = dp[n][i];

			x = n, y = i;

		}

		printf("%d\n",ans);

		if(!ans)continue;

		while(x+y) {

			if(is[x][y])G.push_back(a[x]);

			int x1 = pre[x][y][0];

			int y1 = pre[x][y][1];

			x = x1 , y = y1;

		}

		for(i=G.size()-1; i>=0; i--){

			printf("%d",G[i]);

			i?printf(" "):puts("");

		}

	}

	return 0;

}

/*

2

1 2

3

1 2 3

*/