1829: Candies
| Result | TIME Limit | MEMORY Limit | Run Times | AC Times | JUDGE |
|---|---|---|---|---|---|
 |
3s | 8192K | 816 | 179 | Standard |
All children like candies. One day a group of children are dividing M candies by the following rules.
1. The candies are numbered with 1,2,3…M.
2. One children can select a series of candies from small number to high number.
3. The candy chosen for the first time can be taken away.
4. From the second candy, it can be taken away iff its value is not more than the value of previous one.
Everyone wants to get candies as many as possible. Now assume you are the first child to choose candies, you are to write a program to calculate the largest number of candies you can take.
Input
There may be more than one test case in the input.
The first line of each case is an integer M(M<=1000), number of candies to be divided, followed by M lines indicating values of every candies. They are sorted by their numbers from 1 to M.
Output
For each case, print the answer.
Sample Input
5
5
2
4
1
3
Sample Output
3
This problem is used for contest: 148
#include<iostream>
//#include<cstring>
using namespace std;
int dp[1001];
int a[1001];
int main()
{
int m,i,j;
while(scanf("%d",&m)==1)
{
//memset(dp,0,sizeof(dp));
for(i=1;i<=m;i++)
{
cin>>a[i];
dp[i]=1;
}
//dp[0]=1;
for(i=m;i>=1;i--)
{
for(j=i+1;j<=m;j++)
{
if(a[i]>=a[j]&&dp[i]<dp[j]+1)
{
dp[i]=dp[j]+1;
}
}
}
int maxn=0;
for(i=1;i<=m;i++)
{
if(dp[i]>maxn)
{
maxn=dp[i];
}
}
cout<<maxn<<endl;
}
return 0;
}
//8 6 5 9 3 5 7 6 9