http://acm.pku.edu.cn/JudgeOnline/problem?id=1323貪心是肯定可以的,不過據(jù)說也可以用動(dòng)歸?
我的貪心算法如下: 從n*m 到1依次計(jì)算,如果手里有那個(gè)數(shù), now++ ,否則now--; 記錄下now出現(xiàn)過的最大值,最后輸出最大值
嗯也可以有其他貪心
Source Code
Problem: 1323 User: lnmm
Memory: 64K Time: 0MS
Language: C++ Result: Accepted
Source Code
#include"stdio.h"
int a[51];
int i,j,m,n,max,now,cas=0;
bool have(int x)
{
for(j=1;j<=n;j++)
if(x==a[j])return true;
return false;
}
void main()
{
while(1)
{
cas++;
scanf("%d%d",&m,&n);
if(m==0&&n==0)return;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
max=0;now=0;
for(i=n*m;i>=1;i--)
{
if(have(i)){now++;if(now>max)max=now;}
else now--;
}
printf("Case %d: %d\n",cas,max);
}
}