51Nod 거리 DP+ 스크롤 배열 편집
2369 단어 ACM____동적 기획
제목 링크: 51Nod 편집 거리
사고방식: dp[i][j]로 하여금 A 문자열의 전 i 문자와 B 문자열의 전 j 문자의 최소 편집 거리를 표시하게 한다.
그렇다면,
그리고 i행의 결과는 i-1, i행의 결과와 관계가 있기 때문에 dp[2][MAXLENB] 스크롤 그룹을 사용하여 공간을 최적화할 수 있다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w",stdout)
typedef __int64 LL;
//typedef long long LL;
typedef unsigned int uint;
typedef pair PII;
typedef pair PLL;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int MAXN = 1000 + 5;
const int MAXM = 1000 + 5;
char A[MAXN], B[MAXN];
int dp[2][MAXN];
int main() {
#ifndef ONLINE_JUDGE
FIN;
#endif // ONLINE_JUDGE
while (~scanf("%s %s", A, B)) {
int lenA = strlen(A);
int lenB = strlen(B);
for (int i = 0; i <= lenA; i++) {
for (int j = 0; j <= lenB; j++) {
if (i == 0 && j == 0) dp[i & 1][j] = 0;
else if (i == 0) dp[i & 1][j] = j;
else if (j == 0) dp[i & 1][j] = i;
else if (A[i - 1] == B[j - 1]) dp[i & 1][j] = min(dp[(i - 1) & 1][j - 1], min(dp[(i - 1) & 1][j], dp[i & 1][j - 1]) + 1);
else dp[i & 1][j] = min(dp[(i - 1) & 1][j - 1], min(dp[(i - 1) & 1][j], dp[i & 1][j - 1])) + 1;
}
}
printf("%d
", dp[lenA & 1][lenB]);
}
return 0;
}
좋은 웹페이지 즐겨찾기
