poj 3280 Cheapest Palindrome——DP
9861 단어 heap
우선 추가와 삭제가 똑같다는 것을 발견해야 하기 때문에cost를 선택할 때 delete와dd의 작은 값만 선택하면 됩니다.
상태 전환 방정식:
if(st[i]==st[j])
dp[i][j]=dp[i+1][j-1];
else if(st[i]!=st[j])
dp[i][j]=max(dp[i+1][j]+cost[st[i]-'a'],dp[i][j-1]+cost[st[j]-'a']);
기억화 검색으로 해결하고 있습니다.국경 상황에 주의해라, 그렇지 않으면 수색하여 죽을 것이다.
//time:157MS
//memory:16260K
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
int dp[2005][2010];
int cost[30];
char st[2010];
int min(int a,int b)
{
return a>b?b:a;
}
int DP(int i,int j)
{
if(i==j)
return dp[i][j]=0;
if(dp[i][j]>=0)
return dp[i][j];
if(st[i]==st[j])
{
if(i+1==j)
return dp[i][j]=0;// ， ……
return dp[i][j]=DP(i+1,j-1);
}
else
{
return dp[i][j]=min(DP(i+1,j)+cost[st[i]-'a'],DP(i,j-1)+cost[st[j]-'a']);
}
}
int main(void)
{
int n,m;
while(scanf("%d %d",&n,&m)==2)
{
memset(dp,-1,sizeof(dp));
memset(cost,0,sizeof(cost));
memset(st,0,sizeof(st));
if(!m)
{
puts("0");
continue;
}
scanf("%s",st+1);
int i;
for(i=1;i<=n;i++)
{
char s[10];
int a,b;
scanf("%s %d %d",s,&a,&b);
cost[s[0]-'a']=min(a,b);
}
printf("%d
",DP(1,m));
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준] 13334번: 철로h <= o 라는 조건이 없기 때문에 시작점과 도착점을 통일시켜주기 위해 h <= o 조건을 구현해줍니다. 도착점을 기준으로 오름차순 정렬을 합니다. 0부터 (n-1)까지 순회를 합니다. 최소힙에 시작점을 넣어주고,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
