HDU1423 Greatest Common Increasing Subsequence （DP优化）

LIS和LCS的结合。

容易写出方程，复杂度是nm²，但我们可以去掉一层没有必要的枚举，用一个变量val记录前一阶段的最优解，这样优化成nm。

1<=k<j，j增加1，k的上界也增加1，就可以考虑用变量优化去掉一层循环。

 1 #include<cstdio>

 2 #include<cstring>

 3 #include<algorithm>

 4 using namespace std;

 5 const int maxn=505;

 6 int n,m,T,ans;

 7 int a[maxn],b[maxn],dp[maxn][maxn];

 8

 9 int solve(int *a,int n,int *b,int m){

10     ans=0;

11     memset(dp,0,sizeof(dp));

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

13         int val=0;//记录决策集合S(i,j)中dp[i-1][k]的最大值

14         for(int j=1;j<=m;j++){

15             if(a[i]!=b[j]) dp[i][j]=dp[i-1][j];

16             else dp[i][j]=val+1;

17             if(b[j]<a[i]) val=max(val,dp[i-1][j]);

18             ans=max(dp[i][j],ans);

19         }

20     }

21     return ans;

22 }

23

24 int main(){

25     scanf("%d",&T);

26     while(T--){

27         scanf("%d",&n);

28         for(int i=1;i<=n;i++)

29             scanf("%d",&a[i]);

30         scanf("%d",&m);

31         for(int j=1;j<=m;j++)

32             scanf("%d",&b[j]);

33         printf("%d\n",solve(a,n,b,m));

34         if(T) printf("\n");

35     }

36     return 0;

37 } 

HDU1423 Greatest Common Increasing Subsequence （DP优化）的相关教程结束。