Curriculum Vitae

Curriculum Vitae

时间： 1ms        内存：128M

描述：

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

 

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

 

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

 

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

输入：

第一行包含一个整数n（1≤n≤100）。

第二行包含n个用空格隔开的整数s1，s2，...，sn（0≤si ≤1）。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;
}

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