zoj 1733 || hdu 1159 Common Subsequence(Easy , classics DP)
1566 단어 IM
전에 썼는데 잊어버렸어요.
다시.
번거롭게 생각하기 시작하여 O(N^4)의, 과감한 TLE를 썼다.a열이 i로 끝나고 b열이 j로 끝나는 최대 길이를 기록하기 때문이다.
나중에 생각해 보니 a열 i번째 위치로 가기 전, b열 j 이전의 최대 길이를 직접 기록했다.
만약에 a[i]=b[j]라면 a[i-1][j-1]의 길이는 반드시 1을 더한 다음에 dp[i-1][k], dp[i][k-1]의 최대치를 찾으면 된다.
나의 이전 코드를 보았다 =...그렇게 많은 예처리를 하지 않고 1부터 직렬로 시작하면 돼요. 이 직렬은 0부터 시작해서 예처리를 해서 경계를 넘지 않도록 했어요.
#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define BUG puts("here!!!")
using namespace std;
const int MAX = 1050;
char a[MAX],b[MAX];
int dp[MAX][MAX];
int main()
{
while( ~scanf("%s%s",a,b) )
{
memset(dp,0,sizeof(dp));
int n = strlen(a);
int m = strlen(b);
for(int i=0; i<m; i++)
{
if( a[0] == b[i] )
dp[0][i] = 1;
else
dp[0][i] = ( i == 0 ? 0 : dp[0][i-1] );
}
for(int i=0; i<n; i++)
if( a[i] == b[0] )
dp[i][0] = 1;
else
dp[i][0] = ( i == 0 ? 0 : dp[i-1][0] );
for(int i=1; i<n; i++)
for(int k=1; k<m; k++)
if( a[i] == b[k] )
dp[i][k] = max(dp[i-1][k-1]+1, max(dp[i][k-1], dp[i-1][k]));
else
dp[i][k] = max(dp[i][k-1], dp[i-1][k]);
int ans = dp[n-1][m-1];
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
poj 3624 Charm Bracelet(01 가방 입문문)Charm Bracelet Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10399 Accepted: 4667 Description Bessie has go...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
