這道題寫偽代碼就好了!
Description
Arya has n opponents in the school. Each day he will fight with all opponents who are present this day. His opponents have some fighting plan that guarantees they will win, but implementing this plan requires presence of them all. That means if one day at least one of Arya’s opponents is absent at the school, then Arya will beat all present opponents. Otherwise, if all opponents are present, then they will beat Arya.
For each opponent Arya knows his schedule — whether or not he is going to present on each particular day. Tell him the maximum number of consecutive days that he will beat all present opponents.
Note, that if some day there are no opponents present, Arya still considers he beats all the present opponents.
Input
The first line of the input contains two integers n and d (1?≤?n,?d?≤?100) — the number of opponents and the number of days, respectively.
The i-th of the following d lines contains a string of length n consisting of characters ‘0’ and ‘1’. The j-th character of this string is ‘0’ if the j-th opponent is going to be absent on the i-th day.
Output
Print the only integer — the maximum number of consecutive days that Arya will beat all present opponents.
Sample Input
2 2
10
00
Sample Output
2
題意
有一個人,要和n個人pk,要pk d天
如果這一天所有人都來了,他就輸了
否則這個人就會說勝利
問這個人最多能夠連續勝利多少天
題解:
在這個問題中,我們的目標是找到Arya能夠連續獲勝的最長天數
子結構: 每個子問題是關于從第 i i i天開始 Arya 能夠連勝的天數。在貪婪算法中,我們通過選擇當前能夠獲得最大連勝的方案來逐步構建最優解。
如果當前所有的敵人到齊了,Arya失敗,當前能連勝的天數被重置為0;如果當前敵人沒到齊,也就是輸入的string有一個字符為0,Aray能連勝的天數增加一天。
偽代碼
這道題老師只要求寫偽代碼!
function solution(int n, int d)temp=0ans=0for i=0 to d-1 docan=0input string sfor j=0 to n-1 doif s[j]==0 thencan=1 //once there is one that is absent, Arya can beat them all.breakif can==1 thentemp++else temp=0ans=max{ans,temp}return ans