POJ3280 简单DP
poj3280:http://poj.org/problem?id=3280
简单的多子问题多选择dp问题：
dp[i][j]表示字符下标为i到j的子字符串构成回文的最小消费，构成解的子问题有以下两种情况：
1、str[i]!=str[j]，则最小费用为dp[i][j]=min{dp[i+1][j]+cost(str[i]),dp[i][j-1]+cost[str[j]]}，其中cost(char)，是取得增加和删除该字符的费用较小值；
2、str[i]==str[j]，则最小费用为dp[i][j]=min{dp[i][j],dp[i+1][j-1]}，保证此时dp[i][j]已经求出。

#include <iostream>#include <fstream>#define MAX_DP 2011using namespace std;char str[MAX_DP];unsigned int dp[MAX_DP][MAX_DP];int cost[26];unsigned int min(unsigned int a,unsigned int b){if(a>=b)return b;elsereturn a;}unsigned int dodp(unsigned int start,unsigned int end){if(start>=end)return 0;if(dp[start][end])return dp[start][end];dp[start][end]=min(dodp(start+1,end)+cost[str[start]-'a'],dodp(start,end-1)+cost[str[end]-'a']);if(str[start]==str[end])dp[start][end]=min(dp[start][end],dodp(start+1,end-1));return dp[start][end];}int main(){unsigned int m,n;memset(cost,0,sizeof(cost));memset(dp,0,sizeof(dp));cin>>n>>m;    cin>>str;for(int i=0;i<n;i++){char temp;unsigned int a,b;cin>>temp;cin>>a>>b;cost[temp-'a']=min(a,b);}cout<<dodp(0,m-1)<<endl;return 0;}