动规之区间动规小结

区间动规主要有两种方法：

一、是先想出递归式，然后将之转化为滚动数组。

二、或者从小区间贪到大区间。

POJ 1159 点击打开链接

AC代码如下：

#include
  
   
#include
   
     #include
    
      using namespace std; char a[5005]; short dp[5005][5005]; int min(int a,int b) { return a
     
      >n) { memset(dp,0,sizeof dp); cin>>a+1; //cout<
      
       
 
       
 
       
 
       

 
 
       
POJ 2955 点击打开链接
 
       

 





 
       
AC代码如下：
 
       
 
       
#include
        
         
#include
         
           #include
          
            using namespace std; int dp[105][105]; char str[1005]; int main() { int i,j,o,t; while(cin>>str,str[0]!='e') { int l=strlen (str); for(i=0;i
           
            
 
            
 
            
 
            

 
 
            
POJ 1141 点击打开链接
 
            

 
 
            

 
 
            
AC代码如下：
 
            
 
            
#include
             
              
#include
              
                using namespace std; int dp[205][205]; int dd[205][205]; char str[1005]; int l,minn; int i,j,t,x; void PRINTF(int s,int e) { if(s>e) return ; else { if(s==e) { if(str[s]=='('||str[s]==')') cout<<"()"; else cout<<"[]"; } else{ if(dd[s][e]>=0) { PRINTF(s,dd[s][e]); PRINTF(dd[s][e]+1,e); } else { cout<
               
                dp[i+1][j-1]) { dp[i][j]=dp[i+1][j-1]; dd[i][j]=-1; } } } //cout<
                
                 >str; l=strlen (str); DP(); PRINTF(0,l-1); cout<