#A28. Alvin的商品
Alvin的商品
题目描述
Alvin 的商店的货架由上至下放了 行货架,每行货架由左至右放着 个商品,每个货架的长度一样,一个单位长度,每个商品间没有空隙。有些商品无需增加光照来吸引顾客,用 表示;有些商品则需要人工增加光照,称其为名贵商品,用 表示。
Alvin 家专门有一个商品房可以全天人工光照,最多能放 盆商品,可以将架子上最多 盆名贵商品放入其中增加光照。
为了能够满足所有名贵商品的光照要求,Alvin 决定给每行货架再购买一个补光灯(由于接线问题,一行只能安装一个)每行补光灯的长度必须能从该行最左端的名贵商品一直延伸到最右端的商品(即最右端名贵商品的下标 最左端名贵商品的下标 )。
Alvin 想知道,最多移走 盆名贵商品的情况下,购买架子上的补光灯长度之和最短是多少。
输入格式
第一行三个正整数 。
以下 行,每行 个 或 ,中间无空格,描述 Alvin 架子上的商品。
数据保证,为 的商品的概率为总商品的 。
输出格式
输出最多移走 盆名贵商品去商品房的情况下,购买架子上的补光灯长度之和最短是多少。
输入输出样例
3 5 2
01001
10110
00101
6
样例说明
移走第一行第二个和第二行第一个,货架变为:
00001
00110
00101
而每行的灯必须是连续的,所以灯光要照到的部分为:
00001
00110
00111
总长度之和为 6。
数据范围
对于 的数据:,,。