Looksery Cup 2015 D. Haar Features 暴力
D. Haar Features
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/549/problem/D
Description
Let's consider a rectangular image that is represented with a table of size n × m. The table elements are integers that specify the brightness of each pixel in the image.
A feature also is a rectangular table of size n × m. Each cell of a feature is painted black or white.
To calculate the value of the given feature at the given image, you must perform the following steps. First the table of the feature is put over the table of the image (without rotations or reflections), thus each pixel is entirely covered with either black or white cell. The value of a feature in the image is the value of W - B, where W is the total brightness of the pixels in the image, covered with white feature cells, and B is the total brightness of the pixels covered with black feature cells.
Some examples of the most popular Haar features are given below.
Your task is to determine the number of operations that are required to calculate the feature by using the so-called prefix rectangles.
A prefix rectangle is any rectangle on the image, the upper left corner of which coincides with the upper left corner of the image.
You have a variable value, whose value is initially zero. In one operation you can count the sum of pixel values at any prefix rectangle, multiply it by any integer and add to variable value.
You are given a feature. It is necessary to calculate the minimum number of operations required to calculate the values of this attribute at an arbitrary image. For a better understanding of the statement, read the explanation of the first sample.
Input
Next n lines contain the description of the feature. Each line consists of m characters, the j-th character of the i-th line equals to "W", if this element of the feature is white and "B" if it is black.
Output
Print a single number — the minimum number of operations that you need to make to calculate the value of the feature.
Sample Input
6 8
BBBBBBBB
BBBBBBBB
BBBBBBBB
WWWWWWWW
WWWWWWWW
WWWWWWWW
Sample Output
2
HINT
题意
每次都会使一个前缀矩阵加上任意数,然后问你最小操作数
题解:
数据范围很小,所以直接暴力就好了
代码:
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define test freopen("test.txt","r",stdin)
#define maxn 2000001
#define mod 10007
#define eps 1e-9
int Num;
char CH[];
const int inf=0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fLL;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void P(int x)
{
Num=;if(!x){putchar('');puts("");return;}
while(x>)CH[++Num]=x%,x/=;
while(Num)putchar(CH[Num--]+);
puts("");
}
//************************************************************************************** string s[];
int a[][];
int b[][];
int main()
{
int n=read(),m=read();
for(int i=;i<n;i++)
cin>>s[i];
for(int i=;i<n;i++)
for(int j=;j<m;j++)
if(s[i][j]=='W')
b[i][j]=;
else
b[i][j]=-;
int ans=;
for(int i=n-;i>=;i--)
{
for(int j=m-;j>=;j--)
{
if(a[i][j]!=b[i][j])
{
for(int k=;k<=i;k++)
{
for(int m=;m<=j;m++)
{
a[k][m]+=b[i][j]-a[i][j];
}
}
ans++;
}
}
}
cout<<ans<<endl;
}
最新文章
- 用“MEAN”技术栈开发web应用(三)用mongodb搭建数据库
- 近期C#项目中总结
- css特效
- 优先使用最新版本的IE 和 Chrome 内核 1 <;meta http-equiv=";X-UA-Compatible"; content=";IE=edge,chrome=1";>;
- C++中的Overload、Override和Overwrite
- 基于web的项目管理软件Redmine
- java 类型转换:
- .net 资源
- 转: requestAnimationFrame,Web中写动画的另一种选择
- 浙江工商大学15年校赛E题 无邪的飞行棋 【经典背包】
- Thymeleaf Javascript 取值
- 深究Xcode的bitcode设置
- 一次C++调试记录
- Jmeter关联,正则表达式提取器使用
- 阿里云轻量级服务器上JDK及tomcat部署配置
- jdk 版本切换
- JavaScript中防止重复提交
- JS 将值插入数组中
- 如何解决python 图表中文显示乱码问题(matlplotlib 包)
- SVN与Git比较的优缺点差异