hdu1423 (최대 상승 공용 서열)

23209 단어 dpHDU
이 문제는 본보기로 삼을 수 있다.
#include<iostream>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
using namespace std;
typedef long long lld;
#define oo 0x3f3f3f3f
#define maxn 505
int dp[maxn];
int a[maxn], b[maxn];

int main()
{
	int n, m, T, k;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		scanf("%d", &m);
		for (int i = 1; i <= m; i++)
			scanf("%d", &b[i]);
		memset(dp, 0, sizeof dp);
		for (int i = 1; i <= n; i++)
		{
			k = 0;
			for (int j = 1; j <= m; j++)
			{
				if (b[j]<a[i] && dp[j]>dp[k])
					k = j;
				if (a[i] == b[j] && dp[k] + 1 > dp[j])
					dp[j] = dp[k] + 1;
			} 
		}
		int ans = 0;
		for (int i = 1; i <= m;i++)
		if (dp[i] > ans)
			ans = dp[i];
		printf("%d
", ans); if (T) puts(""); } return 0; } /* 1 5 1 4 2 5 -12 4 -12 1 2 4 */

좋은 웹페이지 즐겨찾기