TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2066
  • 题目
  • P2066粉刷匠
    限制 : 时间限制 : 20000 MS   空间限制 : 65536 KB
    问题描述

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

    输入格式

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

    输出格式

    一个整数,最多能正确粉刷的格子数。

    样例输入 1

    3 6 3
    111111
    000000
    001100

    样例输出 1

    16

    样例输入 2

    1 50 4
    01010110000011100110101000011010100001011001111011

    样例输出 2

    34

    提示

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


    来源  【SCOI2009 day2】