【UVa】Partitioning by Palindromes（dp）-白红宇

【UVa】Partitioning by Palindromes（dp）

阅读量：7240 次

发布时间：2019-06-29

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

设w[i,j]为i-j能分割成的最少回文串

f[i]为前i个字符能够分成的最少回文串

w[i,j]=1 当w[i+1,j-1]==1 && s[i]==s[j] 或 i==j-1 && s[i]==s[j]

w[i,j]=w[i+1,j-1]+2 当s[i]!=s[j]

然后

f[i]=min{f[j]+w[j+1,i], 0<=j<i}

f[0]=0

题目白书有

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             using namespace std;typedef long long ll;#define pii pair
              
               #define mkpii make_pair
               
                #define pdi pair
                
                 #define mkpdi make_pair
                 
                  #define pli pair
                  
                   #define mkpli make_pair
                   
                    #define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a
                    
                     1 && w[i+1][j-1]==1 && s[i]==s[j]) w[i][j]=1; else w[i][j]=w[i+1][j-1]+2; } for1(i, 1, n) rep(j, i) f[i]=min(f[i], f[j]+w[j+1][i]); printf("%d\n", f[n]); } return 0;}