pku1159 Palindrome DP

1642 단어 dp
한 가지 깨달음은 한 무리의 사람들이 틀린 것을 가리키며 억지로 옳다고 말하는 것이다
MLE 후에 답이 최대 5000개라고 생각한 다음에 short int로 바꾸면 된다. A가 떨어진 후에 디스커스를 뒤적인 후에 답은 길이를 빼고 반열과 가장 긴 공공 문자열을 빼는 것이다. = 그때 나는 얼떨결에 손으로 한 조의 데이터를 썼는데 틀린 것 같았다. 그러나 서열이 맞는 것 같았다.
그리고 나는 답장을 눌러 하나하나 보았다.
 / ,         .........
              。。
2011년 댓글이지만 한마디 했어요. 서열인 거 알았으니까 lz가 맞다고요?
어리둥절하다.
알겠습니다. 이제 두 가지 방법을 알았습니다. 하나는 DNA가 일치하는 PKU1141처럼 문자를 추가하는 기본값으로 다른 문자와 일치하는 유사한 구간DP를 쓰는 것입니다.
하나는 원열과 반열의 가장 긴 공통 서열의 길이를 구한 다음에 원열의 길이를 빼면 답이다. 증명도 사실 매우 간단하다. 뇌를 보충하면 만만하고 모두 N2이다.
그리고 스크롤 그룹이 최적화가 된다고 들었는데?그리고 움직여주면 더 작아진다고요?
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define down(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline LL read()
{
	LL d=0,f=1;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
	return d*f;
}
#define N 5005
#define inf 65534
char s[N];
unsigned short int f[N][N];
int n;

int dfs(int i,int j)
{
	if(i>j)return f[i][j]=0;
	if(f[i][j]!=inf)return f[i][j];
	if(s[i]==s[j])
	{
		int ret=dfs(i+1,j-1);
		f[i][j]=ret;
	}else
	{
		int ret1=dfs(i+1,j);
		int ret2=dfs(i,j-1);
		f[i][j]=min(ret1,ret2)+1;
	}
	return f[i][j];
}

int main()
{
	n=read();
	fo(i,1,n)fo(j,1,n)f[i][j]=inf;
	fo(i,1,n)s[i]=getchar();
	cout<<dfs(1,n)<<endl;
	return 0;
}

좋은 웹페이지 즐겨찾기