vijos 1264 神祕的咒語【LICS】

NO IMAGE

連結 :   https://vijos.org/p/1264

描述

身為拜月教的高階間諜,你的任務總是逼迫你出生入死。比如這一次,拜月教主就派你跟蹤趙靈兒一行,潛入試煉窟底。

據說試煉窟底藏著五行法術的最高法術:風神,雷神,雪妖,火神,山神的咒語。為了習得這些法術,要付出艱辛的努力,但是回報同樣十分豐厚。

拜月希望你告訴他咒語的長度為多少。(你:“請問您想知道咒語的具體內容嗎?”拜月:“想,但是vijos不支援special judge。”-_-原來大人物也有大人物的悲哀。。。)
於是你偷偷躲在一邊,想乘機看看咒語究竟是什麼。突然,天空(??試煉窟底看的到天空??)出現了兩條非常長的數字串,你抓狂了。究竟哪個才是真正的咒語呢?你突然想到,這兩個都不是咒語(不妨稱之為偽咒語),而真正的咒語卻與他們有著密切的聯絡。於是你開啟拜月親手給你寫的紙條:”The Real Incantation is Their Common Increasing Subsequence of Maximal Possible Length”
“該死的拜月,居然還會E文!”你咒罵著,但為了一家老小的生命,又不得不賣命地算著咒語的長度。

格式

輸入格式

第一行為1個數N,代表有N組測試資料。

對於每組測試資料,描述了兩條數字串,首先一個數字為一條偽咒語的長度M,接下來M個數描述了偽咒語的內容。

輸出格式

共N行,每行一個數字,描敘了對應咒語的長度。

樣例1

樣例輸入1

1
5 1 4 2 5 -12
4 -12 1 2 4

樣例輸出1

2

限制

1s

提示

對於100%的資料,有1<=N<=5,1<=M<=500,Ai,Bi在長整型範圍內。

題意簡單就是查詢最長公共遞增子序列,自己寫了好幾波都是錯的,所以去網上尋找了一波題解;

題解普遍偏為兩種,就是dp陣列的維數,我個人認為,一維比較簡單粗暴,具體含義見碼中註釋;

#include<bits/stdc  .h>
using namespace std;
const int MAX = 505;
int a[MAX], b[MAX], dp[MAX];///一維dp陣列,此陣列最多存m個數,因為兩序列比較,最長也只能到m;
int main()
{
ios::sync_with_stdio(false);
int N;
cin >> N;
while(N--)
{
int n, m;
cin >> n;
memset(dp, 0, sizeof dp);
for(int i = 0; i < n; i  )
cin >> a[i];
cin >> m;
for(int i = 0; i < m; i  )
cin >> b[i];
int ans = -MAX;
for(int i = 0; i < n; i  )
{
int maxn = 0;
for(int j = 0; j < m; j  )
{
if(a[i] > b[j])///注意判斷條件,因為尋找遞增,所以是">"
maxn = max(maxn, dp[j]);///尋找前面遍歷過的,maxn即為已經找到的最長公共遞增長度;
if(a[i] == b[j])
dp[j] = maxn   1;///如果又發現一隊相等的,則在已知序列長度上加一;
ans = max(ans, dp[j]);
}
}
cout << ans << endl;
}
return 0;
}