POJ3280 Cheapest Palindrome 区间DP - c++编程基础

给你一个字符串，把它变成回文串，可以添加字母也可以删除其中的字母，对于每一个字母添加和删除需要不同的花费，问使得这个字符串变成回文串最少需要花多少

区间DP，从后向前推，如果区间[i,j] s[i] == s[j]，那么dp[i][j] = dp[i+1][j-1], 如果不想等那么要么是加上一个或者删除一个，在这里举个例子把，当推到abcb的时候，操作无非两种删除a或者加上一个a，这两个操作其实是一样的只不过花费不一样，所以可以直接取添加删除中花费较小的那个即可，这样就不用太多的状态转移方程了，一开始添加删除分开写的有点繁琐，写到一半觉得是一样的

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[3000 + 5][3000 + 5]; int cost[1000 + 5]; string s; typedef struct Node { string str; int get,lose; }; Node node[10000 + 5]; void clear() { memset(dp,0,sizeof(dp)); memset(node,0,sizeof(node)); memset(cost,0,sizeof(cost)); } int main() { int n,m; while(cin>>n>>m) { clear(); cin>>s; for(int i=0;i
                    
                     >node[i].str>>node[i].get>>node[i].lose; cost[node[i].str[0] - 'a'] = min(node[i].get,node[i].lose); } for(int i=m-1;i>=0;i--) { for(int j=i+1;j