POJ 3280 Cheapest Palindrome(DP)

时间:2023-03-08 16:06:21
POJ 3280 Cheapest Palindrome(DP)

题目链接

被以前的题目惯性思维了,此题dp[i][j],代表i到j这一段变成回文的最小花费。我觉得挺难的理解的。

 #include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int dp[][];
char s1[];
int hash[];
int main()
{
int n,m,i,j,a,b;
char ch[];
while(scanf("%d%d",&n,&m)!=EOF)
{
scanf("%s",s1);
memset(dp,,sizeof(dp));
for(i = ;i <= n;i ++)
{
scanf("%s%d%d",ch,&a,&b);
hash[ch[]-'a'] = min(a,b);
}
for(i = m;i >= ;i --)
{
for(j = i;j <= m;j ++)
{
if(s1[i-] == s1[j-])
{
dp[i][j] = dp[i+][j-];
}
else
{
dp[i][j] = min(dp[i+][j]+hash[s1[i-]-'a'],dp[i][j-]+hash[s1[j-]-'a']);
}
}
}
printf("%d\n",dp[][m]);
}
return ;
}
/*
2 5
bbaab
a 1 2
b 10 10
*/