|Vijos | 동적 기획 | P1264 신비의 주문

1546 단어 동적 기획Vijos
https://vijos.org/p/1264
LCIS, 즉 최장 상승 공용 서열
dp[I][j]로 a[1.i]와 b[1.j]의 최장 상승 공공 서열을 표시하고 b[j]로 끝냅니다.
dp[I][j] = max(dp[I-1][j], max(dp[I-1][k]+1 | k
이해하지 못하는 강렬한 건의는 스스로 예시를 모의하는 것이다
1
5 1 4 2 5 -12
4 -12 1 2 4
 
  
 
  
 
  
 
  
k     i,j      ,               ,       。

        O(n^2)
 
  
#include
#include  
#include   
#include 
#define ms(i,j) memset(i, j, sizeof(i)); 
using namespace std;
int a[505],b[505];
int f[505];
int m1, m2;
int main()  
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &m1);
		for (int i=1;i<=m1;i++)
		{
			scanf("%d", &a[i]);
		}	
		scanf("%d", &m2);
		for (int i=1;i<=m2;i++)
		{
			scanf("%d", &b[i]);
		}	
		ms(f,0);
		int ans = 0;
		for (int i=1;i<=m1;i++)
		{
			int k = 0;
			for (int j=1;j<=m2;j++)
			{
				if (a[i]==b[j])
				{
					f[j] = max(f[j], f[k]+1);
					ans = max(ans, f[j]);
				}
				else
				{
					if (a[i]>b[j])//a   i       b   j  ,         
					{
						if (f[k]

좋은 웹페이지 즐겨찾기