Palindrome poj 1159

959 단어
제목 링크:http://poj.org/problem?id=1159
제목: 최소한 몇 개의 문 자 를 추가 하면 답장 문자열 이 될 수 있 는 문자열 을 드 리 겠 습 니 다.
ps: 예전 에 했 던 문 제 는 이것 과 비슷 하지만 이것 의 요구 조건 이 더욱 적 기 때문에 상태 와 상태 이전 을 확정 하기 쉽다.그러나 이 문 제 는 int 로 메모 리 를 초과 할 수 있 기 때문에 short 로 만 AC 를 사용 할 수 있 습 니 다. 여기 wa 는 두 번 입 니 다. 간단 한 문제 도 진지 하 게 대해 야 합 니 다.
코드:
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

short dp[5005][5005];
char str[5005];

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        scanf("%s",str+1);
        for(int l=1;l<=n-1;++l){
            for(int i=1;i+l<=n;++i){
                int j=i+l;
                if(str[i]==str[j]){
                    dp[i][j]=dp[i+1][j-1];
                }else{
                    dp[i][j]=min(dp[i][j-1]+1,dp[i+1][j]+1);
                }
            }
        }
        printf("%d
",dp[1][n]); } return 0; }

좋은 웹페이지 즐겨찾기