首页 > 其他 > 详细

poj 3280【区间dp】

时间:2018-02-25 20:23:13      阅读:82      评论:0      收藏:0      [点我收藏+]

标签:题解   cst   串操作   html   最小   iostream   tar   http   urn   

poj 3280

题意:给定一个字符串和每个字符删去和增加的代价,求使字符串变成回文串操作所需的最小代价。

题解:哇!开心!终于亲自做对了!做完这两题这个就回了。uva10739  uva 10453

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 struct st{
 8     int ad,de;
 9 };
10 st a[30];
11 int dp[2050][2050];
12 char s[2050];
13 
14 int main()
15 {
16     int N,len,t1,t2;
17     char t;
18     cin>>N>>len;
19     cin>>s;
20     for(int i=1;i<=N;i++){
21         cin>>t;cin>>t1>>t2;
22         a[t-a].ad=t1,a[t-a].de=t2;
23     }
24     for(int i=0;i<len;i++) dp[i][i]=0;
25     for(int i=len-1;i>=0;i--)
26     {
27         for(int j=i+1;j<len;j++){
28             if(s[i]==s[j])
29                 dp[i][j]=dp[i+1][j-1];
30             else {
31                 dp[i][j]=min(dp[i+1][j]+a[s[i]-a].de,dp[i][j-1]+a[s[j]-a].de);
32                 dp[i][j]=min(dp[i][j],dp[i+1][j]+a[s[i]-a].ad);
33                 dp[i][j]=min(dp[i][j],dp[i][j-1]+a[s[j]-a].ad);
34             }
35         }
36     }
37     cout<<dp[0][len-1]<<endl;
38     return 0;
39 }

 

poj 3280【区间dp】

标签:题解   cst   串操作   html   最小   iostream   tar   http   urn   

原文:https://www.cnblogs.com/zxhyxiao/p/8470050.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号