poj3280Cheapest Palindrome（记忆化）

链接

真的1A了。。

一开始想复杂了 想着补全再删 没想好 后来想到递归 大的回文串是由小的推过来的 

一直递归下去 对于当前的i，j可以选择保留或者删除 选个最小的

#include 
#include
#include
#include
#include
using namespace std;
#define N 2010
#define INF 0xfffffff
int v[500][2];
int dp[N][N];
char s[N];
int dfs(int i,int j)
{
    if(i>j) return 0;
    if(i==j)
    return dp[i][j]=0;
    if(dp[i][j]!=-1)
    return dp[i][j];
    if(s[i]==s[j])
    dp[i][j] = dfs(i+1,j-1);
    else
    dp[i][j] = min(dfs(i,j-1)+min(v[s[j]][0],v[s[j]][1]),dfs(i+1,j)+min(v[s[i]][0],v[s[i]][1]));
    return dp[i][j];
}
int main()
{
    int i,n,m,a,b;
    char c;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(dp,-1,sizeof(dp));
        cin>>s;
        for(i = 1; i <= n; i++)
        {
            cin>>c>>a>>b;
            v[c][0] = a;
            v[c][1] = b;
        }
        int ans = dfs(0,m);
        cout<endl;
    }
    return 0;
}