「RQNOJ155」吞噬比赛
题目描述
镇里举办贪吃比赛，一共比赛N天，规定：每次吃的必须比上次多，一天只能吃一次（撑死…），吃的天数最多的人将获得胜利，获得10000000000 mod 10 的奖金^_^
现在，Sally要参加比赛，她邀请参加OI的你一起帮忙，胜利后七三分成^_^
输入格式第一行一个数N，表示吃的天数（N<=10000)
第二行N个数，表示每天能吃的数量（数量最多10000）
输出格式一个数，表示最多吃的天数
样例输入
6
1 2 3 1 5 6
样例输出
5
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#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; } |
第二种方法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#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; } |
Subscribe