Algorithm/LCIS dp.txt at master · Tachone/Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//复杂度O（n2）
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 510  //字符串长度
int t,m,n,a[N],b[N],f[N][N],prei[N][N],prej[N][N],pi,pj,tag,ans;
void Print(int x,int y)//输出路径
{
    if(f[x][y]==0)
    return;
    if(prei[x][y]!=-1&&prej[x][y]!=-1)
    {
        int px=prei[x][y];
        int py=prej[x][y];
        Print(px,py);
        if(f[x][y]!=f[px][py]&&y!=0)
        {
            cout<<b[y];
            tag++;
            if(tag<ans)
			cout<<" ";
            else
			 cout<<endl;
        }
    }
}
int main()
{
    cin>>t;
    while(t--)
    {
        int i,j;
        cin>>n;
        for(i=1;i<=n;i++)
		cin>>a[i];//a串
        cin>>m;
        for(i=1;i<=m;i++)
	    cin>>b[i];//b串

        memset(f,0,sizeof(f));
        memset(prei,-1,sizeof(prei));
        memset(prej,-1,sizeof(prej));

        for(i=1;i<=n;i++)
        {
            pi=pj=0;
            int maxn=0;
           for(j=1;j<=m;j++)
            {
                f[i][j]=f[i-1][j];
                prei[i][j]=i-1;
                prej[i][j]=j;

                if(a[i]>b[j]&&maxn<f[i-1][j])
				{
					 maxn=f[i-1][j];
					 pi=i-1;
					 pj=j;
				}
                if(a[i]==b[j])
				 {
				    f[i][j]=maxn+1;
					prei[i][j]=pi;
					prej[i][j]=pj;
				 }
            }
        }
        ans=0;
        int flag=-1;
        for(i=1;i<=m;i++)
        {
            if(ans<f[n][i])
            {
                flag=i;
                ans=f[n][i];
            }
        }
        cout<<ans<<endl;
        pi=n,pj=flag;
        tag=0;
        if(pj>0)
           Print(pi,pj);
        if(t!=0)
        cout<<endl;
    }
}


//其实还有一个很风骚的一维的算法。在此基础上压掉了一维空间（时间还是平方）
//。i循环到x的时候，F[i]表示原来F[x][j]。之所以可以这样，
//是因为如果a[i]!=b[j]，因为F[x][j]=F[x-1][j]值不变，F[x]不用改变，
//沿用过去的就好了，和这个比较维护更新得到的max值依然是我们要的。
//而a[i]==b[j]的时候，就改变F[x]的值好了。具体结合代码理解。
#include<cstdio>
#include<cstring>?
int f[1005],a[1005],b[1005],i,j,t,n1,n2,max;
int main()
{
   scanf("%d",&t);
   while(t--)
   {
       scanf("%d%d",&n1,&n2);
       for(i=1;i<=n1;i++)
   		scanf("%d",&a[i]);
       for(i=1;i<=n2;i++)
        scanf("%d",&b[i]);
       memset(f,0,sizeof(f));
        for(i=1;i<=n1;i++)
        {
            max=0;
            for(j=1;j<=n2;j++)
            {
                 if(a[i]>b[j]&&max<f[j])
                   max=f[j];
                  if(a[i]==b[j])
				  f[j]=max+1;
            }
       }
       max=0;
       for(i=1;i<=n2;i++)
        if(max<f[i])
        max=f[i];
        printf("%d\n",max);
}
}