原题目：https://vijos.org/p/1264
题意：求两组数的最长上升公共子序列。
我的做法：
脑残级DP：
dp(i, j) = max{dp(i - 1, k)} , a[i] == b[j] & b[j] < b[k]
= dp[i - 1][j], a[i] != b[j]
然后开三层循环..O(m^3)
然后0.5s过了..
然后发现网上大神有O(m^2)做法..
Orz..这么简单的优化我也想不到..
我已经是条咸鱼了..
我的O(m^3)
[code lang="cpp"]
#include<cstdio>
#include<iostream>
#include<cstring>
//#define INF 2147483649
int n, x[555], y[555], a, b;
int dp[555][555], ans;
using namespace std;
int main(){

scanf("%d", &n);
// cout << n;
while(n--){
ans = 0;
memset(dp, 0, sizeof(dp));
scanf("%d", &a);

x[0] = -2147483644;
y[0] = -2147483644;
for (int i = 1; i <= a; i++) scanf("%d", &x[i]);
scanf("%d", &b);
for (int i = 1; i <= b; i++) scanf("%d", &y[i]);

for (int i = 1; i <= a; i++)
for (int j = 1; j <= b; j++){
if (x[i] == y[j]){
for (int k = 0; k <= j; k++){
if (y[k] < y[j]) dp[i][j] = max(dp[i][j], dp[i - 1][k] + 1);
}
if (x[i] == y[j]) dp[i][j] = max(dp[i][j], 1);
}
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
ans = max(dp[i][j], ans);
}

printf("%d\n", ans);
}
}
[/code]

优化后的O(m^2)
[code lang="cpp"]
#include<cstdio>
#include<iostream>
#include<cstring>
int n, x[555], y[555], a, b;
int dp[555], ans;
using namespace std;
int main(){
scanf("%d", &n);
while(n--){
ans = 0;
memset(dp, 0, sizeof(dp));
scanf("%d", &a);
for (int i = 1; i <= a; i++) scanf("%d", &x[i]);
scanf("%d", &b);
for (int i = 1; i <= b; i++) scanf("%d", &y[i]);
int m;
for (int i = 1; i <= a; i++){
m = 0;
for (int j = 1; j <= b; j++){
if (x[i] > y[j]) m = max(m, dp[j]);
else if (x[i] == y[j]) dp[j] = max(dp[j], m + 1);
ans = max(dp[j], ans);
}
}
printf("%d\n", ans);
}
}
[/code]

不过算是自己想出的第一条比较复杂的DP吧..挺爽的