POJ 3280 Cheapest Palindrome
회문열로 바꾸는 데 필요한 최소한의 문자열을 보여 줍니다.
문제 해결 방법:
하나의 단독 문자에 대해 말하자면, 대칭 위치에 같은 새 자모를 삭제하는 것과 같은 효과가 있다.그래서 삭제할지 추가할지 고민할 필요 없어요.비용이 가장 적게 드는 조작만 사용하면 된다.
dp[i][j]는 i문자에서 j문자까지 회문열에 필요한 최소 비용을 나타낸다.이것은 dp[i+1][j]+의 i자 조작에 대한 최소 비용과 dp[i][j-1]+의 j자 조작에 대한 최소 비용 사이의 최소 값으로만 결정되며 i자 문자가 j자 문자와 같을 때 dp[i+1][j-1]을 더하면 세 개의 최소 값을 판단한다.
다음은 코드입니다.
#include <stdio.h>
char s[2005],c[3];
int dp[2005][2005],cost[27];
int min (int a,int b)
{
if(a>b)a=b;
return a;
}
int main()
{
int n,m,t;
while(scanf("%d%d",&n,&m)!=EOF)
{
scanf("%s",s);
for(int i=0;i<n;i++)
{
scanf("%s",c);
scanf("%d%d",&cost[c[0]-'a'],&t);
if(t<cost[c[0]-'a'])cost[c[0]-'a']=t;
}
for(int i=0;i<m;i++)
{
dp[i][i]=0;
}
for(int i=m-1;i>=0;i--)
{
for(int j=i+1;j<m;j++)
{
dp[i][j]=min(dp[i+1][j]+cost[s[i]-'a'],dp[i][j-1]+cost[s[j]-'a']);
if(s[i]==s[j])dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
}
}
printf("%d
",dp[0][m-1]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
