一个O(N2)的 LCIS DP
f [i] [j] 为 A的前i个元素和B的前J个元素的LCIS。
O(N3) 做法：
此时的代码
1
2
3
4
5
6
7
8
9
10
| for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(a[i]==b[j])
{
for(k=0;k<j;k++)
if(a[i]>b[k]&&f[i][j]<f[i-1][k]+1) f[i][j]=f[i-1][k]+1;
}
else f[i][j]=f[i-1][j];
}
|
优化思路
发现f[i−1][k] 被 重复访问了多次。
因此我们的思路是让k=[1，j），每个k只访问一次
因此我们可以找到之前最大的f[i−1][k]
令它为mx
接下来只需要判断A[i]是否比B[j]大，如果大了，就尝试更新 mx=max(mx,f[i−1][j])
如果$A[i]==B[j] 那么 f[i] [j]=max(f [i] [j] ,mx+1)$
因为f[i][j]是由 $f[i-1] [k] 和 f[i-1] [j] 得到的，但是k已经被压缩成了每个j循环只做一次，因此时间复杂度变成了O(N^2)$
因此我们得到了以下代码
1
2
3
4
5
6
7
8
9
10
11
| for(i=1;i<=n;i++)
{
int mx=0;
for(j=1;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(a[i]==b[j]) f[i][j]=max(f[i][j],mx+1);
else if(a[i]>b[j]) mx=max(mx,f[i-1][j]);
ans=max(ans,f[i][j]);
}
}
|
记住$ mx $每次都要 清空
完整代码如下
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
| #include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
int f[1100][1100];
int n,m;
int a[1100],b[1100];
int t,ans;
int main()
{
ios::sync_with_stdio(false);
int i,j;
cin>>t;
for(t;t>=1;t--)
{
memset(f,0,sizeof(f));
ans=0;
cin>>n;
for(i=1;i<=n;i++) cin>>a[i];
cin>>m;
for(i=1;i<=m;i++) cin>>b[i];
for(i=1;i<=n;i++)
{
int mx=0;
for(j=1;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(a[i]==b[j]) f[i][j]=max(f[i][j],mx+1);
else if(a[i]>b[j]) mx=max(mx,f[i-1][j]);
ans=max(ans,f[i][j]);
}
}
cout<<ans<<endl;
}
return 0;
}
|
一个n^4 或者 n^3 的 dp
已知两个状态 可以从左边或者右边传值给自己
f [i] [j] [k] [l] 表示 第一条路 走到 (i,j) 第二条路 走到 (k,l) 的最大好感度
a[i] [j] 表示 (i,j) 这个人的好感度
因为终点给的值是0，所以末态 是 f [n] [m-1] [n-1] [m] 的值
1
2
3
4
5
6
| for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
for(k=1;k<=n;k++)
for(l=j+1;l<=m;l++)
f[i][j][k][l]=max(max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]),max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]))+a[i][j]+a[k][l];
cout<<f[n][m-1][n-1][m];
|
貌似还有个n^3的优化，因此每一行每一列的i+j都不一样(参考八皇后问题）
悬线法入门
O(NM) 做法
1.设置 l[i] [j] 表示 (i,j)最左边能拓展到的点。
r[i] [j] 表示 (i,j)最右边能拓展到的点。
up[i] [j] 表示能拓展到的最上面的点。
初始化 l[i] [j] = r[i] [j] = j;
mp[i] [j] 表示地图 (i,j) 的状态 。
up[i] [j] 表示 (i,j) 能向上拓展的最大的高度，把它初始化为1。
然后我们可以轻易的推出预处理公式(我们暂时认为 我们要找最大全是1的正方形)
为了简化问题，我们先来看看矩形
如果左边那个点是1，那么这个点就可以向左边拓展，能拓展的最左边的点=上个点能拓展的最左边的点。
同理，右边也是一样。
1
2
3
4
5
6
7
8
9
10
11
| inline void getlr()
{
register int i,j;
for(i=1;i<=n;i++)
for(j=2;j<=m;j++)
if(mp[i][j]==mp[i][j-1]&&mp[i][j]==1) l[i][j]=l[i][j-1];
for(i=1;i<=n;i++)
for(j=m-1;j>=1;j--)
if(mp[i][j]==mp[i][j+1]&&mp[i][j]==1) r[i][j]=r[i][j+1];
return ;
}
|
现在预处理完毕后，我们枚举每个点 (i,j) 能够轻易得到这个点所在的最大矩形宽度a =(r [i] [j] -l [i] [j] +1)
于是横着的问题就解决了，竖着就是 up [i] [j]
因此它的最大面积就是 a*up[i] [j]
那么怎么转移呢？
如果上一个点是 1,这个点也是1的话，那么我们可以得到这个方程
l[i] [j]=max(l[i] [j],l[i-1] [j]), r[i] [j]=min(r[i] [j],r[i-1] [j]),up[i] [j]=up[i-1] [j]+1
别忘了这是个二维矩阵,i可以理解为高度。
于是代码就有了
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
int n,m,up[110][110],l[110][110],r[110][110],ans;
int mp[110][110];
inline void getlr()
{
register int i,j;
for(i=1;i<=n;i++)
for(j=2;j<=m;j++)
if(mp[i][j]==mp[i][j-1]&&mp[i][j]==1) l[i][j]=l[i][j-1];
for(i=1;i<=n;i++)
for(j=m-1;j>=1;j--)
if(mp[i][j]==mp[i][j+1]&&mp[i][j]==1) r[i][j]=r[i][j+1];
return ;
}
inline void dp()
{
register int i,j;
for(i=2;i<=n;i++)
for(j=1;j<=m;j++)
{
if(mp[i][j]==mp[i-1][j]&&mp[i][j]==1) l[i][j]=max(l[i][j],l[i-1][j]),r[i][j]=min(r[i][j],r[i-1][j]),up[i][j]=up[i-1][j]+1;
int a,b;
a=r[i][j]-l[i][j]+1;
b=min(a,up[i][j]);
ans=max(ans,b*b);
}
return ;
}
int main()
{
int i,j;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&mp[i][j]),l[i][j]=r[i][j]=j,up[i][j]=1;
getlr();
dp();
ans=sqrt(ans);
printf("%d",ans);
return 0;
}
|
O(S^2) 做法
S为点数量。
当 N M 极大的时候，上面的nm 做法就会TLE
因此我们有必要学习这个做法。
N,M<=30000
一看就知道不是NM的做法。
S^2的做法很怪，但是可以尽量看下去。
做法很生猛，对于每一个点都来和其他的点比较一下，然后找最大的。
首先排序了一次，让每个点的循环(i)只用对另外每一个点判断一次
设置 l,r,h; 这些东西他们都不是数组了
l，r，h意义和原来差不多。
首先按照高度进行排序
然后 for i,j in [1,s]
然后循环的时候j从i断开。
对于高度比第i小的点单独dp，比他大的单独dp
初始状态 r=m,l=0
对于j<i h=n-q[i].x
对于j>i h=q[i].x
然后比较的时候，r必然向左，l必然向右。
所以得到dp方程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| for(i=1;i<=s;i++)
{
int r=m,l=0,h=n-q[i].x;
for(j=i+1;j<=s;j++)
{
if(h*(r-l)<=ans) break;
ans=max(ans,(q[j].x-q[i].x)*(r-l));
if(q[i].y==q[j].y) break;
if(q[j].y>q[i].y) r=min(r,q[j].y);
if(q[j].y<q[i].y) l=max(l,q[j].y);
}
r=m,l=0,h=q[i].x;
for(j=i-1;j>=1;j--)
{
if(h*(r-l)<=ans) break;
ans=max(ans,(q[i].x-q[j].x)*(r-l));
if(q[i].y==q[j].y) break;
if(q[j].y>q[i].y) r=min(r,q[j].y);
if(q[j].y<q[i].y) l=max(l,q[j].y);
}
}
|
完整代码如下：
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
int n,m,s;
struct que{
int x,y;
}q[10010];
int cmp1(que a,que b)
{
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int cmp2(que a,que b)
{
if(a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
int main()
{
int i,j;
scanf("%d %d",&n,&m);
scanf("%d",&s);
for(i=1;i<=s;i++)
{
scanf("%d %d",&q[i].x,&q[i].y);
}
q[++s].x=0;
q[++s].x=n,q[s].y=0;
q[++s].x=0,q[s].y=m;
q[++s].x=n,q[s].y=m;
int ans=0;
sort(q+1,q+s+1,cmp1);
for(i=1;i<=s;i++)
{
int r=m,l=0,h=n-q[i].x;
for(j=i+1;j<=s;j++)
{
if(h*(r-l)<=ans) break;
ans=max(ans,(q[j].x-q[i].x)*(r-l));
if(q[i].y==q[j].y) break;
if(q[j].y>q[i].y) r=min(r,q[j].y);
if(q[j].y<q[i].y) l=max(l,q[j].y);
}
r=m,l=0,h=q[i].x;
for(j=i-1;j>=1;j--)
{
if(h*(r-l)<=ans) break;
ans=max(ans,(q[i].x-q[j].x)*(r-l));
if(q[i].y==q[j].y) break;
if(q[j].y>q[i].y) r=min(r,q[j].y);
if(q[j].y<q[i].y) l=max(l,q[j].y);
}
}
sort(q+1,q+s+1,cmp2);
for(i=1;i<s;i++) ans=max(ans,(q[i+1].y-q[i].y)*n);
printf("%d",ans);
return 0;
}
|
