街道國的國土只有一個街道。
在這個街道上的每一格可以是一個民宅或是一個水井。因為每個水井的大小不同，所以水井可以供給的人數也不盡相同。而現在，街道國裡的水井不多不少剛好可以供給全國的國民使用。可惜的是街道國的國王街道王是個暴君。他不想要讓人民有太多的接觸；因此，他希望在這個街道上的格與格之間蓋城牆將人民隔開。但是，每個人在不越過城牆前提之下依然要有保有足夠的水井供給。
街道王希望能夠利用這些城牆將人民隔成最多區塊。
輸入的第一行有一個正整數 T，代表測試資料的組數 (1 ≤ T ≤ 200)。
每一組測試資料的第一行有一個整數 N，代表街道國的國土上的格子數，而街道國的國土最少有兩格，最多一萬格。第二行有 N 個數字（A1,A2,...,AN），而且 0 < |Ai| ≤ 10000，按照順序為國土上每一格的民宅裡的人數或水井的大小。如果 Ai > 0，則代表這一格是民宅，而這個民宅裡的人數為 Ai 人。如果 Ai < 0, 則代表這一格是水井，而這個水井可以供給 |Ai| 人。
對每筆測試資料輸出一個整數，代表街道王可以利用城牆所隔成的最多區塊數。
4 4 4 2 −4 −2 5 1 2 −3 3 −3 5 2 −3 4 −4 1 2 1 −1
1 2 1 1
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||