「RQNOJ155」吞噬比赛

2013年11月20日2,9750

题目描述

镇里举办贪吃比赛，一共比赛N天，规定：每次吃的必须比上次多，一天只能吃一次（撑死…），吃的天数最多的人将获得胜利，获得10000000000 mod 10 的奖金^_^

现在，Sally要参加比赛，她邀请参加OI的你一起帮忙，胜利后七三分成^_^

输入格式第一行一个数N，表示吃的天数（N<=10000)

第二行N个数，表示每天能吃的数量（数量最多10000）

输出格式一个数，表示最多吃的天数

样例输入

6
1 2 3 1 5 6

样例输出

代码

#include<iostream>
using namespace std;
int main()
{
    int n,a[10001],f[10001]={0};
    int mx=0;
	cin>>n;
	for(int i=1;i<=n;i++)
    {
    	cin>>a[i];
    }
    f[n]++;
    for(int i=1;i<=n;i++)
    {
       for(int j=i;j>=0;j--)
       {
          if(a[j]<a[i]){f[i]=max(f[j]+1,f[i]);}
      }
      mx=max(f[i],mx);
  }
    cout<<mx;
	return 0;
}

#include<iostream>

using namespace std;

int main()

{

int n,a[10001],f[10001]={0};

int mx=0;

cin>>n;

for(int i=1;i<=n;i++)

{

cin>>a[i];

}

f[n]++;

for(int i=1;i<=n;i++)

{

for(int j=i;j>=0;j--)

{

if(a[j]<a[i]){f[i]=max(f[j]+1,f[i]);}

}

mx=max(f[i],mx);

}

cout<<mx;

return 0;

}

第二种方法

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	int n;
	int a[100001],f[100001],ans=0;
	cin>>n;
	memset(f,127/3,sizeof(f));
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	f[0]=0;
    for(int i=1;i<=n;i++) 
	   for(int j=ans;j>=0;j--)
  	  {
	      	if(a[i]>f[j]){f[j+1]=min(a[i],f[j+1]);ans=max(ans,j+1);break;}
      }
      cout<<ans;
      return 0;
}

#include<iostream>

#include<cstring>

using namespace std;

int main()

{

int n;

int a[100001],f[100001],ans=0;

cin>>n;

memset(f,127/3,sizeof(f));

for(int i=1;i<=n;i++)

{

cin>>a[i];

}

f[0]=0;

for(int i=1;i<=n;i++)

for(int j=ans;j>=0;j--)

{

if(a[i]>f[j]){f[j+1]=min(a[i],f[j+1]);ans=max(ans,j+1);break;}

}

cout<<ans;

return 0;

}

« NOIP2005过河(青蛙过河) 「RQNOJ166」免费午餐 »

hzwer.com _ Home | http://hzwer.com

「RQNOJ155」吞噬比赛

分类目录

热门文章

Myfriends

近期评论