HDU2476 String painter 区间DP - c++编程基础

给你两个字符串s1,s2，问把s1变成s2最少需要几步？变的要求是连续的一段一起变化，语文不好表达不清楚，这题做出的人少，猜猜就是题意有点坑

给出两个串s1和s2，一次只能将一个区间刷一次，问最少几次能让s1=s2

例如zzzzzfzzzzz，长度为11，我们就将下标看做0~10

先将0~10刷一次，变成aaaaaaaaaaa

1~9刷一次，abbbbbbbbba

2~8:abcccccccba

3~7:abcdddddcba

4~6:abcdeeedcab

5:abcdefedcab

这样就6次，变成了s2串了

第二个样例也一样

先将0~10刷一次，变成ccccccccccb

1~9刷一次，cdddddddddcb

2~8:cdcccccccdcb

3~7:cdcdddddcdcb

4~6:cdcdcccdcdcb

5:cdcdcdcdcdcb

最后竟串尾未处理的刷一次

就变成了串2cdcdcdcdcdcd

所以一共7次

很显然，既然是一段一段的变换，想到用区间DP来解决不难，如果直接从s1变到s2，感觉记录的方面比较麻烦的，而且变换注意跟字符对应位置是否相等，再看相等字符之间的区域内来解决；

想简单点，就先判断从空的字符串变化成s2最少需要几步，然后保存下来，再开个数组记录一下s1到s2最少需要几步，dp数组的含义就不用多说了，状态转移方程也不难，主要这题目的变幻挺难的，案例都跑了我好久

#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) string s1,s2; string tmp; int dp[1000 + 5][1000 + 5]; int ans[1000 + 5]; void clear() { memset(ans,0,sizeof(ans)); for(int i=0;i
                    
                     >s1>>s2) { clear(); for(int i=s2.length()-1;i>=0;i--) { for(int j=i+1;j