【CF 682D】String
3801 단어 Stringdp동적 기획codeforcesCF
S, T라는 두 가지 문자열이 있습니다.길이는 각각 n, m.현재 S에서 k문자열을 질서정연하게 선택해야 하며 T에 나타나는 순서는 이 k문자열의 순서와 같다.이 k의 가장 큰 길이와
Solution
동적 기획
가장 좋은 문제를 구하든지 문자열에 있는 문제를 구하든지, 이런 문제는 보자마자 DP라는 것을 안다.구조상태는 f[i][j][k]를 쉽게 떠올릴 수 있다. i는 S의 첫 번째 점과 일치하는 것을 나타내고 j는 T의 첫 번째 점과 일치하는 것을 나타내며 k는 k단을 나눈다.그리고 경기할 때 생각을 하지 않았습니다. 매번 현재의 꿰미가 일치하는지 모르겠고 지난번의 위치를 일일이 열거해야 합니다. 속도도 30%를 넘을 수 밖에 없습니다.
다시 한 번 생각해 보다
우리는 현재 이 문자열이 일치하는지 없는지를 하나의 상태로 저장할 수 있다. 그러면 DP는 1차원을 더하면 f[i][j][k][0,1]로 변하여 i위와 j위가 성공적으로 일치하는지 여부를 나타낸다. 그러면 이동은 매우 명백하다.
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=1007;
int i,j,k,l,t,n,m,ans,kk;
int f[maxn][maxn][11][2];
char s[maxn],st[maxn];
int main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
scanf("%d%d%d",&n,&m,&kk);
scanf("%s",s+1);scanf("%s",st+1);
fo(i,1,n){
fo(j,1,m){
fo(k,1,kk){
f[i][j][k][0]=max(f[i-1][j][k][1],f[i][j-1][k][1]);
f[i][j][k][0]=max(f[i][j][k][0],max(f[i-1][j][k][0],f[i][j-1][k][0]));
if(s[i]==st[j]){
f[i][j][k][1]=f[i-1][j-1][k-1][0]+1;
if(s[i-1]==st[j-1]){
f[i][j][k][1]=max(f[i][j][k][1],f[i-1][j-1][k][1]+1);
}
}
}
}
}
printf("%d
",max(f[n][m][kk][0],f[n][m][kk][1]));
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Access Request, Session and Application in Struts2If we want to use request, Session and application in JSP, what should we do? We can obtain Map type objects such as Req...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
