【bzoj1260】涂色paint[CQOI2007]（区间dp）-白红宇

【bzoj1260】涂色paint[CQOI2007]（区间dp）

阅读量：6345 次

发布时间：2019-06-22

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

　　题目传送门：

　　这道题其实和有点像，然而做过原题的我居然没看出来。。思想僵化。。

　　首先，题目中每次染色的是一段连续区间，大概就能想到区间dp，于是我们可以设$ f[l][r] $表示区间$ [l,r] $需要染的次数。

　　转移的话，首先我们可以把区间$ [l,r] $拆成两部分分别染，此时$ f[l][r]=\min \left\{f[l][k]+f[k+1][r] \right\} \ (l<=k<r) $，答案就是$ f[1,n] $。

　　此外如果第$ l $和$ r $个位置颜色相同，还可以同时染色，这样有三种情况：

　　1、把区间$ [l,r] $染色，然后继续染区间$ f[l+1,r-1] $，此时$ f[l][r]=f[l+1][r-1]+1 $；

　　2、对于区间$ [l+1,r] $的染色方案中把位置$ r $染上色的区间，将其左端点拉到位置$ l $，使位置$ l $染上色，此时$ f[l][r]=f[l+1][r] $；

　　3、对于区间$ [l,r-1] $的染色方案中把位置$ l $染上色的区间，将其右端点拉到位置$ r $，使位置$ r $染上色，此时$ f[l][r]=f[l][r-1] $；

　　于是这样转移方程就胡出来了。。

　　代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #define ll long long#define ull unsigned long long#define max(a,b) (a>b?a:b)#define min(a,b) (a
               
                >=1){ if(b&1)ans=ans*a%mod; a=a*a%mod;} return ans;}inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}inline void swap(int &a,int &b){ int tmp=a; a=b; b=tmp;}using namespace std;int f[60][60];char s[60];int n;int main(){ scanf("%s",s); n=strlen(s); memset(f,0x3f,sizeof(f)); for(int i=1;i<=n;i++)f[i][i]=1; for(int i=2;i<=n;i++) for(int l=1;l<=n-i+1;l++){ int r=l+i-1; if(s[l-1]==s[r-1])f[l][r]=min(f[l+1][r-1]+1,min(f[l+1][r],f[l][r-1])); for(int k=l;k

bzoj1260

转载于:https://www.cnblogs.com/quzhizhou/p/9383469.html

你可能感兴趣的文章