poj 3280 Cheapest Palindrome ---(DP 回文串)
题目链接：http://poj.org/problem?id=3280
思路： dp[i][j] :=第i个字符到第j个字符之间形成回文串的最小费用。
dp[i][j]=min(dp[i+1][j]+cost[s[i-1]-'a'],dp[i][j-1]+cost[s[j-1]-'a']);
if(s[i-1]==s[j-1]) dp[i][j]=min(dp[i+1][j-1],dp[i][j]);
注意循环顺序，我觉得这题就是这里是tricky：
#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>using namespace std;const int MAX_M=2005;int dp[MAX_M][MAX_M],cost[26];int main(){int N,M;while(cin>>N>>M){string s;cin>>s;for(int i=0;i<N;i++){char ch;int ca,cb;cin>>ch>>ca>>cb;cost[ch-'a']=min(ca,cb);}memset(dp,0,sizeof(dp));for(int j=1;j<=M;j++){for(int i=j-1;i>=1;i--){dp[i][j]=min(dp[i+1][j]+cost[s[i-1]-'a'],dp[i][j-1]+cost[s[j-1]-'a']);if(s[i-1]==s[j-1]) dp[i][j]=min(dp[i+1][j-1],dp[i][j]);}}cout<<dp[1][M]<<endl;}return 0;}