POJ 3280 Cheapest Palindrome 구간 dp
사고방식: dp[i][j]는 i~j 구간이 회문열로 변하는 최소 비용을 나타낸다. 현재 dp[i][j]를 요구한다고 가정하면 그의 동네 간의 모든 최우수치를 알 수 있다.
예를 들어 dp[i][j]는 dp[i][j]에서 머리로 구성된 메모 문자열 dp[i+1][j]+delete[i]와 dp[i][j]에 꼬리로 구성된 메모 문자열 dp[i+1][j]+add[s[i]를 추가하여 최소값을 얻는다.
같은 이치: dp[i][j]가 dp[i][j]에서 끝부분으로 구성된 메모줄 dp[i][j-1]+delete[s[j]와 dp[i][j]에 머리로 구성된 메모줄 dp[i][j-1]+add[s[j]를 추가하여 최소값을 얻는다.
만약:s[i]=s[j]라면 s[i][j]는 s[i+1][j-1]의 기초 위에서 양쪽 끝이 이미 하나의 회문이다. dp[i][j]=min(dp[i][j], dp[i+1][j-1])
상태 전환 방정식:
if(s[i] == s[j]) dp[i][j] = min(dp[i][j],dp[i+1][j-1])
dp[i][j] = min(dp[i][j],dp[i+1][j]+add[s[i]]);
dp[i][j]= min(dp[i][j],dp[i][j-1]+add[s[j]]);
코드:(구간을 순환 조건으로 함)
#include
#include
#include
#include
using namespace std;
int add[200];
int dp[2009][2009];
char s[2009];
int main()
{
int N,M;
scanf("%d%d",&N,&M);
cin>>(s+1);
for(int i = 1; i<=N; i++)
{
char ch;
int a,b;
cin>>ch>>a>>b;
add[ch] = min(a,b);
}
for(int i = 1; i<=M; i++)dp[i][i] = 0;
for(int l = 1; l<=M; l++)
{
for(int i = 1; i+l<=M+1; i++)
{
int j= i+l-1;
dp[i][j] = 0x3f3f3f3f;// ，
if(s[i]==s[j])dp[i][j] = dp[i+1][j-1];
dp[i][j]= min(dp[i][j],dp[i+1][j]+add[s[i]]);
dp[i][j]= min(dp[i][j],dp[i][j-1]+add[s[j]]);
}
}
printf("%d
",dp[1][M]);
return 0;
} 구간을 조건으로 하지 않고 dp[i][j]를 알려면 dp[i+1][j-1]과 같은 종류를 알아야 한다. 따라서 기점은 반드시 뒤에서 앞으로 밀어야 한다. 마지막으로 구한 것은 dp[1][M]이다. 따라서 뒤의 동네가 끊임없이 앞으로 통합되고 코드는 다음과 같다.
#include
#include
#include
#include
#include
using namespace std;
int n,m,dp[2009][2009],in[27],de[27];
char ch[2009];
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",ch);
for (int i=1;i<=n;i++)
{
char c;
cin>>c;
int k1,k2;
scanf("%d%d",&k1,&k2);
in[c-'a']=k1;de[c-'a']=k2;
}
for (int i=m-1;i>=0;i--) //
{
dp[i][i]=0;
for (int j=i+1;j 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
