BZOJ 1260&UVa 4394 区间DP-白红宇

BZOJ 1260&UVa 4394 区间DP

阅读量：4654 次

发布时间：2019-06-09

本文共 4063 字，大约阅读时间需要 13 分钟。

题意:

　　给一段字符串成段染色,问染成目标串最少次数.

SOL:

　　区间DP...

　　DP[i][j]表示从i染到j最小代价

　　转移:dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);

CODE:

　　BZ:

/*=================================================================# Created time: 2016-03-28 21:10# Filename: uva4394.cpp# Description: =================================================================*/#define me AcrossTheSky #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
               #include 
               
                 #include 
                
                  #include 
                 
                   #define lowbit(x) (x)&(-x) #define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++) #define FORP(i,a,b) for(int i=(a);i<=(b);i++) #define FORM(i,a,b) for(int i=(a);i>=(b);i--) #define ls(a,b) (((a)+(b)) << 1) #define rs(a,b) (((a)+(b)) >> 1) #define getlc(a) ch[(a)][0] #define getrc(a) ch[(a)][1] #define maxn 500#define maxm 100000 #define pi 3.1415926535898 #define _e 2.718281828459 #define INF 1070000000 using namespace std; typedef long long ll; typedef unsigned long long ull; template
                  
                    inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*==================split line==================*/ char A[maxn],C[maxn];int dp[maxn][maxn],ans[maxn];int main(){ freopen("a.in","r",stdin); //while (scanf("%s",C)!=EOF){ scanf("%s",A); //FORP(i,0,maxn) B[i]=''; int n=strlen(A); memset(dp,0,sizeof(dp)); FORP(i,0,n-1) FORP(j,i,n-1) dp[i][j]=INF; FORP(i,0,n-1) dp[i][i]=1; FORP(l,1,n-1) FORP(i,0,n-1-l) { int j=i+l; dp[i][j]=dp[i+1][j]+1; FORP(k,i+1,j) if (A[k]==A[i]) dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]); } printf("%d",dp[0][n-1]); //FORP(i,0,n-1) // FORP(j,i,n-1) printf("%d%c",dp[i][j],j==n-1?'\n':' '); /*memset(ans,0,sizeof(ans)); ans[0]=(A[0]!=C[0]); FORP(i,1,n-1) if (A[i]==C[i]) ans[i]=ans[i-1]; else { ans[i]=dp[0][i]; FORP(j,0,i-1) ans[i]=min(ans[i],ans[j]+dp[j+1][i]); } printf("%d\n",ans[n-1]); }*/}

UVa:

/*=================================================================# Created time: 2016-03-28 21:10# Filename: uva4394.cpp# Description: =================================================================*/#define me AcrossTheSky #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
               #include 
               
                 #include 
                
                  #include 
                 
                   #define lowbit(x) (x)&(-x) #define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++) #define FORP(i,a,b) for(int i=(a);i<=(b);i++) #define FORM(i,a,b) for(int i=(a);i>=(b);i--) #define ls(a,b) (((a)+(b)) << 1) #define rs(a,b) (((a)+(b)) >> 1) #define getlc(a) ch[(a)][0] #define getrc(a) ch[(a)][1] #define maxn 500#define maxm 100000 #define pi 3.1415926535898 #define _e 2.718281828459 #define INF 1070000000 using namespace std; typedef long long ll; typedef unsigned long long ull; template
                  
                    inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*==================split line==================*/ char A[maxn],C[maxn];int dp[maxn][maxn],ans[maxn];int main(){ freopen("a.in","r",stdin); while (scanf("%s",C)!=EOF){ scanf("%s",A); //FORP(i,0,maxn) B[i]=''; int n=strlen(A); memset(dp,0,sizeof(dp)); FORP(i,0,n-1) FORP(j,i,n-1) dp[i][j]=INF; FORP(i,0,n-1) dp[i][i]=1; FORP(l,1,n-1) FORP(i,0,n-1-l) { int j=i+l; dp[i][j]=dp[i+1][j]+1; FORP(k,i+1,j) if (A[k]==A[i]) dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]); } //FORP(i,0,n-1) // FORP(j,i,n-1) printf("%d%c",dp[i][j],j==n-1?'\n':' '); memset(ans,0,sizeof(ans)); ans[0]=(A[0]!=C[0]); FORP(i,1,n-1) if (A[i]==C[i]) ans[i]=ans[i-1]; else { ans[i]=dp[0][i]; FORP(j,0,i-1) ans[i]=min(ans[i],ans[j]+dp[j+1][i]); } printf("%d\n",ans[n-1]); }}