点个关注点个赞吧
-
一道比较简单的线性dp题目
前置知识：会手推一些简单的状态转移方程、较为熟练地掌握背包问题模型
[SCOI2009]粉刷匠
题目描述
windy有 \(N\) 条木板需要被粉刷。 每条木板被分为 \(M\) 个格子。 每个格子要被刷成红色或蓝色。
windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。
如果windy只能粉刷 \(T\) 次，他最多能正确粉刷多少格子？
一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。
输入格式
第一行包含三个整数，\(N\) \(M\) \(T\)。
接下来有\(N\)行，每行一个长度为\(M\)的字符串，'\(0\)'表示红色，'\(1\)'表示蓝色。
输出格式
包含一个整数，最多能正确粉刷的格子数。
样例 #1
样例输入 #1
3 6 3
111111
000000
001100
样例输出 #1
16
提示
\(30%\)的数据，满足 \(1 <= N,M <= 10 ； 0 <= T <= 100\) 。
\(100%\)的数据，满足 \(1 <= N,M <= 50 ； 0 <= T <= 2500\) 。