POJ3280 简单DP
poj3280:http://poj.org/problem?id=3280简单的多子问题多选择dp问题：
dp表示字符下标为i到j的子字符串构成回文的最小消费，构成解的子问题有以下两种情况：
1、str!=str，则最小费用为dp=min{dp+cost(str),dp+cost]}，其中cost(char)，是取得增加和删除该字符的费用较小值；
2、str==str，则最小费用为dp=min{dp,dp}，保证此时dp已经求出。
#include <iostream>#include <fstream>#define MAX_DP 2011using namespace std;char str;unsigned int dp;int cost;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)return dp;dp=min(dodp(start+1,end)+cost-'a'],dodp(start,end-1)+cost-'a']);if(str==str)dp=min(dp,dodp(start+1,end-1));return dp;}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=min(a,b);}cout<<dodp(0,m-1)<<endl;return 0;}
页:
[1]