首页 > 代码库 > LCIS tyvj1071 DP优化

LCIS tyvj1071 DP优化

2024-07-07 02:30:34   229人阅读

思路：

　　f[i][j]表示n1串第i个与n2串第j个且以j结尾的LCIS长度。

　　很好想的一个DP。

　　

　　然后难点是优化。这道题也算是用到了DP优化的一个经典类型吧。

　　可以这样说，这类DP优化的起因是发现重复计算了很多状态，比如本题k的那层循环。

　　然后就可以用maxl标记搞一下，将O(n^3)变成O(n^2).

 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 3100
int n1[MAXN],n2[MAXN];
int n;
int f[MAXN][MAXN];
int ff[MAXN];

inline void deal(int &x,int y)
{
        x=max(x,y);
}
int main()
{
        //freopen("input.txt","r",stdin);
        //freopen("output.txt","w",stdout);
        int i,j;
        scanf("%d",&n);
        for (i=1;i<=n;i++)
        {
                scanf("%d",&n1[i]);
        }
        for (i=1;i<=n;i++)
        {
                scanf("%d",&n2[i]);
        }
        memset(f,0,sizeof(f));
        memset(ff,-INF,sizeof(ff));
        f[0][0]=0;
        int maxl=0;
        for (i=1;i<=n;i++)
        {
                maxl=0;
                for (j=1;j<=n;j++)
                {
                        if (n1[i]>n2[j])deal(maxl,f[i-1][j]);
                        if (n1[i]==n2[j])
                        {
                                deal(f[i][j],maxl+1);
                                                   /*             for (k=j-1;k>=0;k--)
                                {
                                        if (n2[k]<n2[j])deal(f[i][k],f[i-1][k]);
                                }*/
                        }else
                        {
                                deal(f[i][j],f[i-1][j]);
                            
                        }
                }
        }
        int ans=0;
        for (i=1;i<=n;i++)
        {
                deal(ans,f[n][i]);
        }
        cout<<ans<<endl;
}

 


联系
我们