poj 3280 Cheapest Palindrome DP

题目连接：http://poj.org/problem?id=3280

题意就是给你一个字符串，含有n个字母，每个字母可以添加可以去除，添加和删除字母有花费，问组成一个回文串。

思路就是每个回文串的最大子串必定有一个开头一个结尾位置，最终位置为0~len-1,这样但是每一对起始位置都会有一个回文长度，对每一个长度进行搜就可以了。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#define loop(s,i,n) for(i = s;i < n;i++)
#define cl(a,b) memset(a,b,sizeof(a))
using namespace std;
using namespace std;
const int maxn = 2005;

int dp[maxn][maxn];
int add[30], del[30];

int main(){
    int n, m, i, j, len;
    char c, str[maxn];
    cin >> n >> m >> str;
    loop(0,i,n)
    {
        cin >> c;
        cin >> add[c-'a'] >> del[c-'a'];
    }
    loop(1,len,m)
        for(i = 0; i + len < m; i ++){
            j = i + len;
            if(str[i] == str[j]){
                dp[i][j] = dp[i+1][j-1];
            }else{
                dp[i][j] = min(
                    min(dp[i+1][j]+add[str[i]-'a'], dp[i][j-1]+add[str[j]-'a']),
                    min(dp[i+1][j]+del[str[i]-'a'], dp[i][j-1]+del[str[j]-'a']));
            }
        }
    cout<<dp[0][m-1]<<endl;
    return 0;
}