Codeforces 225C Barcode(矩阵上DP)

题目链接：http://codeforces.com/contest/225/problem/C

题目大意：

给出一个矩阵，只有两种字符'.'和'#'，问最少修改多少个点才能让每一列的字符一致，且字符一致的连续的列的宽度在x和y之间。

解题思路：

先求出每列‘.’和'#'的前缀和，sum[i][0]表示前i列'#' 的前缀和，sum[i][1]表示前i列'.' 的前缀和 ,因为修改要求每列都保持一直，其实我们可以将每列都当成一个点来看，那样我们就相当于是在一维序列上操作了。

dp[i][0]表示最后一列为'.'的最优解，dp[i][1]表示最后一列为'#'的最优解。

那么我们可以得到状态转移方程：

dp[i+j][0]=min(dp[i+j][0],dp[i][1]+sum[i+j][0]-sum[i][0])，x=<j<=y，0<=i<=m
dp[i+j][1]=min(dp[i+j][1],dp[i][0]+sum[i+j][1]-sum[i][1])，x=<j<=y，0<=i<=m

其实很好理解，dp[i+j][0]表示第i+j列为'.'，那么可以由相差为j的第i列为'#'的状态推导过来，同时要将i+1~j的'#'都变为'.'

dp[i+j][1]同理。

代码：

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 #include<string>

 #include<string.h>

 #include<cctype>

 #include<math.h>

 #include<stdlib.h>

 #include<stack>

 #include<queue>

 #include<set>

 #include<map>

 #define lc(a) (a<<1)

 #define rc(a) (a<<1|1)

 #define MID(a,b) ((a+b)>>1)

 #define fin(name)  freopen(name,"r",stdin)

 #define fout(name) freopen(name,"w",stdout)

 #define clr(arr,val) memset(arr,val,sizeof(arr))

 #define _for(i,start,end) for(int i=start;i<=end;i++)

 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

 using namespace std;

 typedef long long LL;

 const int N=3e3+;

 const LL INF64=1e18;

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 int dp[N][];  //dp[i][0]表示最后一列为'.'的最优解，dp[i][1]表示最后一列为'#'的最优解

 int sum[N][]; //sum[i][0]表示前i列'#' 的前缀和，sum[i][1]表示前i列'.' 的前缀和 

 int main(){

     memset(dp,0x3f,sizeof(dp));

     FAST_IO;

     int n,m,x,y;

     cin>>n>>m>>x>>y;

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

         for(int j=;j<=m;j++){

             char x;

             cin>>x;

             if(x=='#')

                 sum[j][]++;

             else

                 sum[j][]++;

         }

     }

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

         sum[i][]+=sum[i-][];

         sum[i][]+=sum[i-][];

     }

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

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

         for(int j=x;j<=y;j++){

             dp[i+j][]=min(dp[i+j][],dp[i][]+sum[i+j][]-sum[i][]);

             dp[i+j][]=min(dp[i+j][],dp[i][]+sum[i+j][]-sum[i][]);

         }

     }

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

     return ;

 }

巴特西

Codeforces 225C Barcode(矩阵上DP)

最新文章

热门文章