CF思维联系–CodeForces - 225C. Barcode(二路动态规划)
Desciption
You’ve got an n × m pixel picture. Each pixel can be white or black. Your task is to change the colors of as few pixels as possible to obtain a barcode picture.
A picture is a barcode if the following conditions are fulfilled:
All pixels in each column are of the same color.
The width of each monochrome vertical line is at least x and at most y pixels. In other words, if we group all neighbouring columns of the pixels with equal color, the size of each group can not be less than x or greater than y.
Input
The first line contains four space-separated integers n, m, x and y (1 ≤ n, m, x, y ≤ 1000; x ≤ y).
Then follow n lines, describing the original image. Each of these lines contains exactly m characters. Character “.” represents a white pixel and “#” represents a black pixel. The picture description doesn’t have any other characters besides “.” and “#”.
Output
In the first line print the minimum number of pixels to repaint. It is guaranteed that the answer exists.
Examples
input
6 5 1 2
##.#.
.###.
###…
#…#
.##.#
###…
output
11
input
2 5 1 1
…
output
5
Note
In the first test sample the picture after changing some colors can looks as follows:
.##…
.##…
.##…
.##…
.##…
.##…
In the second test sample the picture after changing some colors can looks as follows:
.#.#.
.#.#.
-------------------------****-------------------
先把每列修改的数量保存下来,都变成#的花费,和都变成‘ . ’的花费,这样状态就变成了第i列,就变成一个普通DP题。
为什么是二路动态规划,是因为一开始的选择有两种,虽然一开始的颜色是有大有小的,但是基于动态规划,当前最优解并不一定是全局最优,所以这一点我们把它们分成两部分。
这道题思考起来没有那没有那么复杂,讨论第i列染或不染(变成#或不变)但是无论染或不染都要至少染或不然连续的X以上,且不可超过Y列,那么就是说当换状态时如果变成另一种状态一定是从另一种状态的连续的x到Y列变化而来,而不改变状态时就是连续的一种状态,累加当前状态的消耗。进而得到状态转移方程
for(int k=x;k<=y;k++){
dp[i][j][0]=min(dp[i][j][0],dp[i-1][k][1]+cnt[i][0]);
dp[i][j][1]=min(dp[i][j][1],dp[i-1][k][0]+cnt[i][1]);
}
进而可得出代码
#include <bits/stdc++.h>
using namespace std;
template <typename t>
void read(t &x)
{
char ch = getchar();
x = 0;
int f = 1;
while (ch < '0' || ch > '9')
f = (ch == '-' ? -1 : f), ch = getchar();
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchar();
x *f;
}
#define wi(n) printf("%d ", n)
#define wl(n) printf("%lld ", n)
#define P puts(" ")
typedef long long ll;
#define MOD 1000000007
#define mp(a, b) make_pair(a, b)
//---------------https://lunatic.blog.csdn.net/-------------------//
const int maxn = 1005;
const int INF = 0x3f3f3f3f;
int cnt[maxn][2];
int dp[maxn][maxn][2];
int main()
{
int m, n, x, y;
read(m),read(n),read(x),read(y);
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
char x;
scanf(" %c", &x);
if (x == '#')
cnt[j][1]++;
else
cnt[j][0]++;
}
}
memset(dp, 0x3f, sizeof(dp));
for (int i = 0; i < n; i++)
{
if (i == 0){
for (int k = 0; k < 2; k++)
dp[i][1][k] = cnt[i][k];
continue;
}
for (int j = 1; j <= i+1&& j <= y; j++)
{
if (j == 1)
{
for (int k = x; k <= y; k++)
{
dp[i][1][1] = min(dp[i - 1][k][0] + cnt[i][1], dp[i][1][1]);
dp[i][1][0] = min(dp[i - 1][k][1] + cnt[i][0], dp[i][1][0]);
}
}
else
{
dp[i][j][1] = dp[i - 1][j - 1][1] + cnt[i][1];
dp[i][j][0] = dp[i - 1][j - 1][0] + cnt[i][0];
}
}
}
int ans = INF;
for (int i = x; i <= y; i++)
{
ans = min(dp[n - 1][i][0], min(dp[n - 1][i][1], ans));
}
wi(ans);
P;
}
这个代码我调了三个小时,写出来之后!不知道为什么前边用cin输入这个题就过不了,而且每组样例都能本地AC。尴尬,求解?
最新文章
- 如何搞定IE+google双内核的360浏览器表单自动回填兼容问题
- css3动画之背景颜色的自动切换
- 用c#开发微信 (20) 微信登录网站 - 扫描二维码登录
- BZOJ 2303 方格染色
- java利用commons-email发送邮件并进行封装
- MongoDBAuth
- asp.net [AjaxMethod]
- 记录OC学习的一点一滴(二)
- win10 uwp 读写XML
- 【建图+拓扑判环】BZOJ3953: [WF2013]Self-Assembly
- ServiceStack.Redis 请求次数6000次异常
- 搭建docker私有仓库
- MySQL数据库的sql语句的导出与导入
- 成功使Linux服务端和Windows客户端建立socket通信
- 《python for data analysis》第四章,numpy的基本使用
- 【学习】Python进行数据提取的方法总结【转载】
- 从Java小白到收获BAT等offer,分享我这两年的经验和感悟
- Light OJ 1116
- 【Checkio Exercise】Three Point Circle
- golang学习笔记14 golang substring 截取字符串
热门文章
- Dubbo 路由机制的实现
- 用Jenkins集成ios项目设置多scheme,同一代码自动输出多个环境包 实现便捷切换API环境
- ASP.NET Core中的Action的返回值类型
- Salesforce考试 | 如何维护我的Salesforce认证
- 小程序运行时如何助力传统APP转型?
- 用一个完整的案例讲解Python数据分析的整个流程和基础知识
- 熬夜整理出来的干货:Python+Pycharm+PyQT5可视化程序设计入门
- E2. Send Boxes to Alice (Hard Version)
- Python刷CSDN阅读数(仅供娱乐)
- 使用mysqlbinlog查看二进制日志