http://acm.pku.edu.cn/JudgeOnline/problem?id=1323贪心是肯定可以的,不过据说也可以用动归?
我的贪心算法如下: 从n*m 到1依次计算,如果手里有那个数, now++ ,否则now--; 记录下now出现过的最大值,最后输出最大值
嗯也可以有其他贪心
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);
}
}