这题一开始把我给坑了,我还没知道LCIS的算法,然后就慢慢搞吧,幸运的是还真写出来了,只不过麻烦了一点。
我是将该题转换为多条线段相交,然后找出最多多少条不相交,并且其数值死递增的。
代码如下:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[][];
int list1[],list2[];
struct Edge{
int val,vex[];
int pos;
}p[];
void init()
{
int i,j;
for(i=;i<=;i++)
for(j=;j<=;j++)
dp[i][j]=;
for(i=;i<=;i++)
p[i].pos=;
} int main()
{
int t,n,m,i,j,k,r,f;
scanf("%d",&t);
while(t--)
{
init();
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%d",&list1[i]);
scanf("%d",&m);
for(i=;i<=m;i++)
scanf("%d",&list2[i]);
int f=;
for(i=;i<=n;i++)
{
for(j=;j<=m;j++)
{
if(list1[i]==list2[j])
{
p[i].val=list1[i];
p[i].vex[p[i].pos++]=j;
f=;
}
}
}
/*for(i=1;i<=n;i++)
{
cout<<" ** "<<p[i].val<<" ** :";
for(j=0;j<p[i].pos;j++)
cout<<p[i].vex[j]<<" ";
cout<<endl;
}*/
int Max=;
if(f)
Max=;
for(i=;i<=n;i++)
{
for(j=;j<i;j++)
{
if(p[i].val>p[j].val)
{
//cout<<"ok"<<endl;
//cout<<p[i].val<<" "<<p[j].val<<endl;
for(k=;k<p[i].pos;k++)
{
for(r=;r<p[j].pos;r++)
{
if(p[i].vex[k]>p[j].vex[r])
dp[i][p[i].vex[k]]=max(dp[i][p[i].vex[k]],dp[j][p[j].vex[r]]+);
if(dp[i][p[i].vex[k]]>Max)
{
Max=dp[i][p[i].vex[k]];
//cout<<Max<<endl;
}
}
}
}
}
}
printf("%d\n",Max);
if(t)
printf("\n");
}
return ;
}
正解的代码有如下两种版本,一种是一维数组,一种二维。思想是一样的。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[][],a[],b[];
int LCIS(int n,int m)
{
int i,j,k,temp;
int ans=;
memset(dp,,sizeof(dp));
for(i=;i<=n;i++)
{
temp=;
for(j=;j<=m;j++)
{
dp[i][j]=dp[i-][j];
if(a[i]==b[j]) dp[i][j]=temp+;
if(a[i]>b[j]&&dp[i-][j]>temp)
temp=dp[i-][j];
if(ans<dp[i][j])
ans=dp[i][j];
}
}
return ans;
}
int main()
{
int t,n,m,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for(i=;i<=m;i++)
scanf("%d",&b[i]);
printf("%d\n",LCIS(n,m));
if(t)
printf("\n");
}
}
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[],a[],b[];
int LCIS(int n,int m)
{
int i,j,k;
memset(f,,sizeof(f));
for(i=;i<=n;i++)
{
k=;
for(j=;j<=m;j++)
{
if(a[i]==b[j])
f[j]=max(f[j],k+);
if(a[i]>b[j]&&f[j]>k)
k=f[j];
//cout<<k<<endl;
}
}
int ans=;
for(i=;i<=m;i++)
ans=max(ans,f[i]);
return ans;
}
int main()
{
int t,n,m,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for(i=;i<=m;i++)
scanf("%d",&b[i]);
printf("%d\n",LCIS(n,m));
if(t)
printf("\n");
}
}