LCS模板
#include <bits/stdc++.h>
using namespace std
;
const int N
= 1000;
int dp
[N
][N
];
char A
[N
], B
[N
];
int main()
{
fgets(A
+ 1, N
, stdin);
fgets(B
+ 1, N
, stdin);
int lenA
= strlen(A
+1);
int lenB
= strlen(B
+1);
for(int i
= 0; i
<= lenA
; i
++)
{
dp
[i
][0] = 0;
}
for(int j
= 0; j
<= lenB
; j
++)
{
dp
[0][j
] = 0;
}
for(int i
= 1; i
<= lenA
; i
++)
{
for(int j
= 1; j
<= lenB
; j
++)
{
if(A
[i
] == B
[j
])
{
dp
[i
][j
] = dp
[i
-1][j
-1] + 1;
}
else
{
dp
[i
][j
] = max(dp
[i
-1][j
], dp
[i
][j
-1]);
}
}
}
cout
<< dp
[lenA
-1][lenB
] << endl
;
return 0;
}
题解思路
这道题既可以用最长不下降子序列求解 也可以用最长公共子序列 不过由于可以有重复元素所以状态方程跟模板不同，需要做修改
if(A
[i
] == B
[j
])
{
dp
[i
][j
] = max(dp
[i
-1][j
], dp
[i
][j
-1]) + 1;
}
else
{
dp
[i
][j
] = max(dp
[i
-1][j
], dp
[i
][j
-1]);
}
AC代码
#include <bits/stdc++.h>
using namespace std
;
const int maxn
= 10010;
int A
[maxn
], B
[maxn
];
int dp
[maxn
][maxn
];
map
<int, int> mp
;
int main()
{
int n
;
cin
>> n
;
int m
;
cin
>> m
;
for(int i
= 1; i
<= m
; i
++)
{
cin
>> A
[i
];
}
int l
;
cin
>> l
;
for(int j
= 1; j
<= l
; j
++)
{
cin
>> B
[j
];
}
for(int i
= 0; i
<= m
; i
++)
{
dp
[i
][0] = 0;
}
for(int j
= 0; j
<= l
; j
++)
{
dp
[0][j
] = 0;
}
for(int i
= 1; i
<= m
; i
++)
{
for(int j
= 1; j
<= l
; j
++)
{
if(A
[i
] == B
[j
])
{
dp
[i
][j
] = max(dp
[i
-1][j
], dp
[i
][j
-1]) + 1;
}
else
{
dp
[i
][j
] = max(dp
[i
-1][j
], dp
[i
][j
-1]);
}
}
}
cout
<< dp
[m
][l
];
return 0;
}
