本文主要是介绍Codeforces Round #139 (Div. 2) C. Barcode，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给定n*m的矩阵 只有 # or . 要求 每列通过修改后 只存在 # 或者 . ，并且同种符号 连续的列数 q 满足 x<=q <=y 求满足这些条件 修改点数的最小数量
数据保证 可以达到目标。
设dp[i][j][k] i大小 1000 表示 第i列 , j 0 或1 分别表示当前 #号连续或者 . 号连续 ，k 大小 1000 表示 对应j的 列连续个数dp的值表示 达到当前状态 的最小修改次数。
由 dp[i][0][j] 可得 dp[i][0][j+1] (j<y) , dp[i][1][1] (j>x)
由 dp[i][1][j] 可得 dp[i][1][j+1] (j<y) , dp[i][0][1] (j>x)
//还SB似得 写了一发DFS 果断超时
code :
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 1000000000
#define N 1003
int n,m,x,y,dp[N][2][N],d[N][2];
char str[N][N];
int main()
{//freopen("in.txt","r",stdin);scanf("%d%d%d%d",&n,&m,&x,&y);for(int i=1;i<=n;i++){scanf("%s",str[i]+1);}for(int i=1;i<=m;i++){int sum=0;for(int j=1;j<=n;j++){if(str[j][i]=='#') sum++;}d[i][0]=sum; d[i][1]=n-sum;}for(int i=0;i<=m;i++){for(int j=0;j<=y;j++)dp[i][0][j]=dp[i][1][j]=INF;}dp[0][0][0]=dp[0][1][0]=0;for(int i=1;i<=m;i++){for(int j=0;j<=y;j++){if(dp[i-1][0][j]<INF ){if(j<y)dp[i][0][j+1]=min(dp[i][0][j+1],dp[i-1][0][j]+d[i][1]);if(j>=x)dp[i][1][1]=min(dp[i][1][1],dp[i-1][0][j]+d[i][0]);}if(dp[i-1][1][j]<INF){if(j<y)dp[i][1][j+1]=min(dp[i][1][j+1],dp[i-1][1][j]+d[i][0]);if(j>=x)dp[i][0][1]=min(dp[i][0][1],dp[i-1][1][j]+d[i][1]);}}}int mi=INF;for(int i=x;i<=y;i++){mi=min(mi,dp[m][0][i]);mi=min(mi,dp[m][1][i]);}printf("%d\n",mi);return 0;
}
这篇关于Codeforces Round #139 (Div. 2) C. Barcode的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
