교내 시뮬레이션 - 변형lcs
1572 단어 dp
그 시간의 복잡도는 분명히 문제가 있었다...그러나 우리는lcs가 반드시 <=1e3이라는 것을 발견할 수 있기 때문에 f[i][j]로 b의 앞 i개 안에lcs의 길이가 j라는 것을 나타낸다.
f[i][j]는 우리가 방금 비슷한 방식으로 emmm를 옮길 수 있다.아이디어는 i번째 자모가 가장 긴 공공 서열의 일원이 될 수 있는지를 고려하는 것이다.
마지막으로 출력은 i의 가장 큰 합법적인 f[m][i]를 찾아서 i를 출력하면 됩니다.
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=100006;
const int maxm=1006;
int dp[maxm][maxm];
int lena,lenb;
char s1[maxn],s2[maxm];
int nxt[27][maxn];
int wle;
int main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%s",s1+1);
scanf("%s",s2+1);
lena=strlen(s1+1);
lenb=strlen(s2+1);
memset(dp,inf,sizeof dp);
memset(nxt,inf,sizeof nxt);
for (int i=0;i<26;++i){
for (int j=lena;j>=0;j--){
nxt[i][j]=nxt[i][j+1];
if (s1[j]-'a'==i)nxt[i][j]=j;
}
}
// for (int i=0;i<26;++i){
// printf("
%c:",(char)('a'+i));
// for (int j=0;j<=lena;++j){
// printf("%d ",nxt[i][j]);
// }
// }
// puts("-1-1-");
for (int i=0;i<=lena;++i)dp[i][0]=0;
for (int i=1;i<=lenb;++i)
{
for (int j=1;j<=i;++j)
{
// printf("%d %d
",i,j);
// system("PAUSE");
dp[i][j]=dp[i-1][j];
if (dp[i-1][j-1]<=lena) dp[i][j]=min(dp[i][j],nxt[s2[i]-'a'][dp[i-1][j-1]+1]);
}
}
// puts("010101");
for (int i=0;i<=lenb;++i){
if (dp[lenb][i]==inf)break;
wle=i;
}
printf("%d
",wle);
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
