D. Flood Fill 区间DP 或lcs匹配

题意给定一串数字相同的连续的数字可以同时转换成一个相同数字问最小几次可以全部转换成一个相同的数字

法1：区间dp dp[l][r][0/1] 0表示l r区间转化成和最左边相同需要多少次 1表示转化成和最右边相同区间dp即可

 #include<bits/stdc++.h>

 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)

 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr))

 #define F first

 #define S second

 #define pii pair<int ,int >

 #define mkp make_pair

 #define pb push_back

 using namespace std;

 typedef long long ll;

 const int maxn=5e3+;

 int c[maxn],a[maxn],b[maxn];

 int dp[maxn][maxn][];

 int main(){

     int n;

     MS(dp,0x3f3f3f3f);

     scanf("%d",&n);

     FOR(i,,n)scanf("%d",&c[i]);

     int cnt=;

     int p=;

     while(p<=n){

         if(c[p]!=c[p-]||p==)a[++cnt]=c[p];

         p++;

     }

     for(int i=;i<=cnt;i++){

         dp[i][i][]=dp[i][i][]=;

     }

     for(int len=;len<=cnt;len++){

         for(int l=,r=len+l;r<=cnt;r++,l++){

             dp[l][r][]=min(dp[l][r][],dp[l+][r][]+);

             dp[l][r][]=min(dp[l][r][],dp[l+][r][]+!(a[r]==a[l]));

             dp[l][r][]=min(dp[l][r][],dp[l][r-][]+);

             dp[l][r][]=min(dp[l][r][],dp[l][r-][]+!(a[l]==a[r]));

         }

     }

     cout<<min(dp[][cnt][],dp[][cnt][])<<endl;

     return ;

 }

法2：LCS 从题目可以看出如果转换成n个互相不连续的数字之后，如果所有数字都不相同则需要转换n-1次才能转换成一种答案

如果存在例如1 2 3 4 2 5 有区间[2,5] 这时如果先转化2 5 之间的数字即可少转化一次那么问题就转换成求最大不相交的这种区间有多少个（相交不行，因为相交中间夹的那个点就被更改了）

而求最大相交的区间有多少个就是把原序列翻转后的序列和原序列求lcs 因为lcs配对的过程在原序列中的i 和翻转序列的j 就相当于在原序列左右两边配对所以不会相交而因为是翻转的序列所以会求两遍

所以要/2 并且有一个区间的左右是重合的也就退化成了一个点，不能算（这里在除以2的时候已经被消气了）减1 是因为没有区间的时候是n-1的，每多一个区间都可以-1 这样答案就是总共的点数n-1-floor(lcs(s)/2);

 #include<bits/stdc++.h>

 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)

 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr))

 #define F first

 #define S second

 #define pii pair<int ,int >

 #define mkp make_pair

 #define pb push_back

 using namespace std;

 typedef long long ll;

 const int maxn=5e3+;

 int c[maxn],a[maxn],b[maxn];

 int dp[maxn][maxn];

 int main(){

     int n;

     scanf("%d",&n);

     FOR(i,,n)scanf("%d",&c[i]);

     int cnt=;

     int p=;

     while(p<=n){

         if(c[p]!=c[p-]||p==)a[++cnt]=c[p];

         p++;

     }

     memcpy(b,a,sizeof(a));

     reverse(b+,b+cnt+);

 //    for(int i=1;i<=cnt;i++)cout<<b[i]<<" ";

 //    puts("");

     for(int i=;i<=cnt;i++){

         for(int j=;j<=cnt;j++)

         {

             if(a[i]==b[j]){

                 dp[i][j]=dp[i-][j-]+;

             }

             else dp[i][j]=max(dp[i-][j],dp[i][j-]);

         }

     }

     printf("%d\n",cnt--dp[cnt][cnt]/);

     return ;

 }

两种方法参考：https://www.cnblogs.com/pkgunboat/p/10361375.html

区间dp 参考：https://blog.csdn.net/moon_sky1999/article/details/87171499

巴特西

D. Flood Fill 区间DP 或lcs匹配

最新文章

热门文章