[CODEVS1520] 메모 문자열(dp)

3189 단어 문제풀이dp

제목 설명


전송문

문제풀이


바보 같은 문제가 나로 하여금 여러 번 WA를 하게 했다.codevs는 gets로 정말 똥을 먹을 수 없습니다 = f (i, j) 를 설정하면 i~j 이 단락에 최소한 몇 개를 삽입할 수 있는지 표시합니다.그러면
f(i,j)={f(i+1,j−1),s[i]=s[j]min{f(i+1,j),f(i,j+1)}+1
상기 두 가지 조건은if와else가 될 수 없다는 것을 주의해야 한다. 즉, s[i]=s[j]가 만족하든 만족하지 않든min을 취해야 한다. 왜냐하면 가장 좋은 해답은 어디에서 얻었는지 보장할 수 없기 때문이다.
초기화
f(i,i)=1,f(i,i+1)={0,s[i]=s[i+1]1,s[i]!=s[i+1]
처음에 f(i,i+1)가 s[i]를 빠뜨렸어요!s[i+1]의 경우.역시 내가 너무 어리석었어.

코드

#include
#include
#include
using namespace std;
#define N 1005

char s[N];
int n,f[N][N];

void in()
{
    char ch=getchar();
    while (ch<'0'&&ch>'z') ch=getchar();
    while (ch>='0'&&ch<='z') s[++n]=ch,ch=getchar();
}
int main()
{
    in();
    memset(f,127,sizeof(f));
    for (int i=1;i<=n;++i) f[i][i]=0;
    for (int i=1;iif (s[i]==s[i+1]) f[i][i+1]=0;
        else f[i][i+1]=1;

    for (int len=3;len<=n;++len)
        for (int l=1;l<=n-len+1;++l)
        {
            int r=l+len-1;
            if (s[l]==s[r]) f[l][r]=min(f[l][r],f[l+1][r-1]);
            f[l][r]=min(f[l][r],f[l+1][r]+1);
            f[l][r]=min(f[l][r],f[l][r-1]+1);
        }
    printf("%d
",f[1][n]);
}
UIKit로 개발한 최적의 뷰 편~
rubyXl에서 excel이 파괴되는 것을 피하기 위해 조심스럽게 조작하면서 내용의 주의사항을 변경합니다

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage