1296: [SCOI2009]粉刷匠

1296: [SCOI2009]粉刷匠

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 916  Solved: 532

[Submit][Status]

Description

windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷,只能选择一条木板上一段连续的格子,然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次,他最多能正确粉刷多少格子? 一个格子如果未被粉刷或者被粉刷错颜色,就算错误粉刷。

Input

输入文件paint.in第一行包含三个整数,N M T。 接下来有N行,每行一个长度为M的字符串,'0'表示红色,'1'表示蓝色。

Output

输出文件paint.out包含一个整数,最多能正确粉刷的格子数。

Sample Input

3 6 3 111111 000000 001100

Sample Output

16

HINT

30%的数据,满足 1 <= N,M <= 10 ; 0 <= T <= 100 。 100%的数据,满足 1 <= N,M <= 50 ; 0 <= T <= 2500 。

Source

Day2

题解:这个。。。再一次感天动地地没犯脑残(phile:。。。) ,好了思路——首先通过dp然后求出来对于每一层上面的状况——即对于前i个单位,刷j次可以获得多少的面积,然后直接用来玩背包问题,分组背包哦。。。详见《背包九讲》(传送门

1 var
 2    n,m,t,ll,i,j,k,l,a1:longint;
 3    a:array[0..100] of longint;
 4    b,c:array[0..100,0..10000] of longint;
 5    c1:char;
 6 function max(x,y:longint):longint;inline;
 7          begin
 8               if x>y then max:=x else max:=y;
 9          end;
10 function min(x,y:longint):longint;inline;
11          begin
12               if x<y then min:=x else min:=y;
13          end;
14 begin
15      readln(n,m,t);
16      for i:=1 to n do
17          begin
18               for j:=1 to m do
19                   begin
20                        read(c1);
21                        a[j]:=a[j-1]+ord(c1)-48;
22                   end;
23               readln;
24               for j:=1 to m do
25                   for k:=1 to m do
26                       begin
27                            b[k,j]:=0;
28                            for l:=0 to k-1 do
29                                begin
30                                     a1:=a[k]-a[l];
31                                     b[k,j]:=max(b[k,j],b[l,j-1]+max(a1,k-l-a1))
32                                end;
33                       end;
34               for j:=1 to t do
35                   begin
36                        a1:=min(m,j);
37                        for k:=1 to a1 do
38                            c[i,j]:=max(c[i,j],c[i-1,j-k]+b[m,k]);
39                   end;
40          end;
41      for i:=1 to t do
42          ll:=max(ll,c[n,i]);
43      writeln(ll);

44 end.     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏智能计算时代

数据科学家用得最多的十种数据挖掘算法

Latest KDnuggets Poll asked Which methods/algorithms you used in the past 12 mon...

36270
来自专栏数据科学学习手札

(数据科学学习手札03)Python与R在随机数生成上的异同

随机数的使用是很多算法的关键步骤,例如蒙特卡洛法、遗传算法中的轮盘赌法的过程,因此对于任意一种语言,掌握其各类型随机数生成的方法至关重要,Python与R在随机...

29970
来自专栏HansBug's Lab

1084: [SCOI2005]最大子矩阵

1084: [SCOI2005]最大子矩阵 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1325  Sol...

45750
来自专栏机器之心

教程 | 如何使用TensorFlow中的高级API:Estimator、Experiment和Dataset

选自Medium 作者:Peter Roelants 机器之心编译 参与:李泽南、黄小天 近日,背景调查公司 Onfido 研究主管 Peter Roelant...

75670
来自专栏Flutter入门

Android OpenGL ES(二)-正交投影

平移矩阵和单位矩阵和类似。但是向量[x,y,z,1]前乘这个平移矩阵后的结构就是平移矩阵中定义的偏移量。

39310
来自专栏数值分析与有限元编程

可视化 | Tecplot作三角形单元后处理工具

对于有限元分析的后处理,除了单的信息,还包括单元信息,比如一个单元由哪些结点组成。Tecplot可以处理的单元类型有三角形单元,四边形单元,四面体单元和六面体单...

41240
来自专栏转载gongluck的CSDN博客

H.264格式分析

一.H.264基本流结构 H.264 的基本流(elementary stream,ES)的结构分为两层,包括视频编码层(VCL)和网络适配层(NAL)。视频编...

79950
来自专栏小樱的经验随笔

从零基础学三分查找

今晚是我们学长第二次讲课,讲了一个三分!认真听了一下,感觉不是很难,可能会比二分还简单些!我就把上课讲的内容归纳为一篇文章概述吧!以后也会重点讲解的! 简单点说...

456100
来自专栏数据结构与算法

2039 骑马修栅栏

题目描述 Description Farmer John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒的人...

384110
来自专栏数据小魔方

机器学习笔记——哑变量处理

在机器学习的特征处理环节,免不了需要用到类别型特征,这类特征进入模型的方式与一般数值型变量有所不同。

74230

扫码关注云+社区

领取腾讯云代金券