1756 . Ch2. Section 1. 學務處的服務
TopCoder
Tags
Description
“咻~~~蹦”
“啊啊~♥……”
“不要啦~♥……”
經過了一番激戰後，妹妹的同學們都被妁艷打倒了，她們倒在地上，十分的虛弱，不過至少妁艷已經幫她們解放了。
“印象中在要下課之前有看了一下時間…之後就甚麼都不記得了…”
“你…你是要來找妹妹的啊…那…就不要再看著我們了嘛>//////<”
妁艷又在教室內望了望，還是見不到妹妹的蹤影。雖然說教室內還有好多學生，只要問一些問題AC了她們或許能得到更多的線索，不過妁
艷還是決定離開了這裡，繼續尋找妹妹。
妁艷一走出教室，不自覺的望了周遭……在月光的照耀下，看到了隔壁棟樓的屋頂上站著一位長髮飄逸的女生…，雖然那不像妹妹，卻深
深的把妁艷吸引了過去。
妁艷到了隔壁樓，發現要到屋頂必須先打開一大門。但門被鎖住了，於是他就前往學務處找鑰匙了。
一進到學務處，燈突然都亮了，當然門一定也被關上了，然後妁艷才發現，學務處內有好多的學生，她們都處在被控制的狀態，呆呆的望
著妁艷，
“葛格~葛格~你上次怎麼可以那樣對我>///////< ?”
“對嘛葛格壞壞~你要補償我們~♥”
“來做愛校服務吧揪咪~♥”
“要好好服務我們喔，要……”
“不!不要!...”還好妁艷沒有被迷惑到，”那我就如你們所願，來幫你們解放吧!”
妁艷站在學務處的最左邊，在他面前有n排的學生，每排有m個人。
妁艷的武器有了新裝備後，可在瞬間發出大範圍的光波，只要被照到的學生就會感到無比的幸福並倒下，然後魔力被吸光，魔法就解除
了。
不過因為學生們有身高的差異，對於一個學生，只要她的前方有任何一個學生身高跟他一樣高或著更高來擋住光的話，她就不會被妁艷攻
擊到。所以妁艷就必須攻擊許多次了。
還有，每次攻擊妁艷都可以控制攻擊的範圍，也就是可以攻擊相鄰連續的幾行，不過要注意的是，如果這幾行中，只要有一行已經沒有敵
人，光芒就會照到學務處右側，反彈並射中妁艷，妁艷就會感到無比的幸福並倒下。
當然，妁艷希望攻擊的次數最少，於是他給你了n排m個學生的身高，希望你幫他求出最少的攻擊次數。
Input Format
測資可能會有許多筆
每一筆測資會先有兩個數字n、m(1≤n,m≤100000) (總學生人數≤100000)
再來會有n行，每行m個數字，數字代表學生們的身高
妁艷就站在這些學生的左方
Output Format
對於每一筆輸出一行
輸出最少攻擊次數
Sample Input 1
1 2 3 4 5
3 2 3 4 3
3 2 3 5 6
Sample Output 1
Hints
範測:
_________1 2 3 4 5 (第一行)
妁艷_____3 2 3 4 3 (第二行)
_________3 2 3 5 6 (第三行)
第一次照1到3行:
(*代表被照到)
* * * * *
* 2 3 * 3
* 2 3 * *
第二次照2到3行:
* * * * *
* * * * 3
* * * * *
第三次照第2行:
* * * * *
* * * * *
* * * * *
三次就OK了~
Problem Source
原TIOJ1756 / problem setter: lnsuyn
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 16 |
| 2 | 1 | 16 |
| 3 | 2 | 16 |
| 4 | 3 | 16 |
| 5 | 4 | 16 |
| 6 | 5 | 20 |