Curriculum Vitae

时间: 1ms        内存:128M

描述:

Hideo Kojima刚辞去Konami的工作。现在他将找到一个新的工作场所。尽管他是一个知名人士,但他仍然需要一份简历来申请工作。

 

在他的职业生涯中,已经制作了n个游戏。其中一些是成功的,有些则不是。Hideo希望从他的简历中删除其中几个,以便给雇主留下更好的印象。因此,在他的简历中,成功的游戏后应该没有不成功的游戏。

 

更正式地说,给你一个值为01的数组s1s2sn。零对应于不成功的游戏,一对应于成功的游戏。游戏是按照它们制作的顺序给出的,Hideo不能交换这些值。他应该从这个数组中删除一些元素,使得这个数组在一之后不会出现零。

 

除此之外,Hideo还想在他的简历中提及尽可能多地游戏。帮助他确定可以在他的简历中留下的最大游戏数量。

输入:

第一行包含一个整数n1n100)。

第二行包含n个用空格隔开的整数s1s2sn0si1)。0对应于不成功的游戏,1对应于成功的游戏。

输出:

一个整数 – Hideo可以在他的简历中留下的最大游戏数量,以便在成功之后不会出现不成功的游戏。

示例输入:

4
1 1 0 1

示例输出:

3

提示:

参考答案(内存最优[1120]):

#include<stdio.h>
int n;
int a[200];
int dp[200];
int max(int x,int y)
{
	return x>y?x:y;
}
int main()
{
	int maxi=0;
	int yes=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		dp[i]=1;
		if(a[i]==0)
		for(int j=1;j<i;j++)
		{
			if(a[j]==0)
			{
				dp[i]=max(dp[i],dp[j]+1);
			}
 		}
 		if(a[i]==1)
 		for(int j=1;j<i;j++)
 		{
			dp[i]=max(dp[i],dp[j]+1);
		}
		maxi=max(maxi,dp[i]);
	}
	printf("%d",maxi);
}

参考答案(时间最优[2]):

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
const int maxn=105;

int a[maxn];
int dp[maxn][2];

int main()
{
    int n;
    memset(dp,0, sizeof(dp));
    scanf("%d",&n);
    for (int i = 1; i <=n ; ++i) {
        scanf("%d",&a[i]);
    }
    int ans=0;
    for (int i = 1; i <=n ; ++i) {
            int t=0;
           for (int j = 1; j <=i ; ++j) {
               if(a[j]==0)
                   t++;
           }
           for (int j = i; j <=n ; ++j) {
               if(a[j]==1)
                   t++;
           }
           ans=max(ans,t);
    }
    printf("%d\n",ans);
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。