拦截导弹

问题描述 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹 能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系 统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹的枚数和导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，每个数据之间至少有一个空 格），计算这套系统最多能拦截多少导弹。

输入

第1行有1个整数n，代表导弹的数量。 （n的高度数据是不大于30000的正整数）

输出

输出这套系统最多能拦截多少导弹。

输入复制

8

389 207 155 300 299 170 158 65

输出复制

6

#include<bits/stdc++.h>
using namespace std;
int n;
int a[110]={0};
int b[110]={0};
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=0;i<n;i++)
	{
		b[i]=1;
		for(int j=0;j<i;j++)
		{
			if(a[j]>a[i])
			{
				b[i]=max(b[i],b[j]+1);
			}
		}
	}
	cout<<b[n-1];
	
	
	return 0;
}

取数问题

题目描述 设有 N 个正整数（1≤N≤50），其中每一个均是大于等于 1 小于等于 300 的数。 从这 N 个数中任取出若干个数（不能取相邻的数），要求得 到一种取法，使得到的和为最大。 例如：当 N=5 时，有 5个数分别为：13,18,28,45,21； 此时，有许多种取法， 如： 13,28,21 和为 62； 13,45 和为 58； 18,45 和为 63；

输入

第一行是一个整数 N； 第二行有 N 个符合条件的整数。

输出

一个整数，即最大和。

输入复制

5

13 18 28 45 21

输出复制

63

#include<bits/stdc++.h>
using namespace std;
int n;
int a[110]={0};
int b[110]={0};
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=0;i<n;i++)
	{
		b[i]=a[i];
		for(int j=0;j<i;j++)
		{
			b[i]=max(b[i-1],a[i]+b[i-2]);
		}
	}
	cout<<b[n-1];
	
	
	return 0;
}

跳格子

题目描述：地面上有一排长度为n的格子1一n，每个格子上都有一个数xi，开始时你在位置0，每次你可以向前跳1-2格，然后取走格子上的数，直到跳到位置n+1。取走的数的和就是你的得分，现在你想知道你可能的最大得分是多少。

输入
一行四个整数n,A,B,C(n≤100000,0≤A,B,C≤10000)，其中n表示格子的数量。x[i]由如下方式生成:

for(int i=1;i<=n;i++)
{
	int tmp=((long long)a*i*i+b*i+c)%20000;
	x[i]=tmp-10000;
}

输出

一行一个整数，表示ans的最大得分

输入复制

3 1 1 1

输出复制

-9993

#include<bits/stdc++.h>
using namespace std;
int n;
int x,y,z;
int a[110]={0};
int b[110]={0};
int main()
{
	cin>>n>>x>>y>>z;
	for(int i=1;i<=n;i++)
	{
		int tmp=((long long)x*i*i+y*i+z)%20000;
		a[i]=tmp-10000;
	}
	b[1]=a[1];
	for(int i=2;i<=n+1;i++)
	{
		b[i]=max(b[i-1]+a[i],b[i-2]+a[i]);
	}
	cout<<b[n+1];
	
	
	return 0;
}

前缀最大和

题目描述 求一个数列的所有前缀最大值之和。 即：给出长度为 n 的数列 ai,求出对于所有 1≤i≤n，max(a1,a2,...,ai) 的和。 比如，有数列：666 304 692 188 596，前缀最大值为：666 666 692 692 692，和为 3408。 对于每个位置的前缀最大值解释如下：对于第 1 个数 666 ，只有一个数，一定最大；对于 第 2 个数，求出前两个数的最大数，还是 666 ；对于第 3 个数，求出前 3 个数的最大数是 692…… 其余位置依次类推，最后求前缀最大值得和。由于读入较大，数列由随机种子生成。其 中 a[1]=x，a[i]=(379×a[i−1]+131)mod997（mod 代表求余数）

输入

一行两个正整数 n, x ，分别表示数列的长度和随机种子。(n≤100000,x<997)

输出

一行一个正整数表示该数列的前缀最大值之和。

输入复制

5 666

输出复制

3408

#include<bits/stdc++.h>
using namespace std;
int n,m;
int x,y,z;
int a[110]={0};
int b[110]={0};
int main()
{
	cin>>n>>a[0];
	for(int i=1;i<n;i++)
	{
		a[i]=(379*a[i-1]+131)%997;
	}
	b[0]=a[0];
	m+=b[0];
	for(int i=1;i<n;i++)
	{
		b[i]=max(a[i],b[i-1]);
		m+=b[i];
	}
	cout<<m;
	
	
	return 0;
}

跳格子2

问题描述 地面上有一排长度为n的格子1-n，每个格子上都有一个数xi，开始时你在位置0，每次你可以向前跳1-2格，然后取 走格子上的数，直到跳到位置n+1。取走的数的和就是你的得分，现在你想知道你可能的最小得分是多少。

输入

一行四个整数n,A,B,C(n≤100000,0≤A,B,C≤10000)，其中n表示格子的数量。x[i]由如下方式生成：

for(int i=1;i<=n;i++)
{
	int tmp=((long long)a*i*i+b*i+c)%20000;
	x[i]=tmp-10000;
}

输出

一行一个整数ans表示可能的最小得分

输入复制

3 1 1 1

输出复制

-29977

#include<bits/stdc++.h>
using namespace std;
int n;
int x,y,z;
int a[110]={0};
int b[110]={0};
int main()
{
	cin>>n>>x>>y>>z;
	for(int i=1;i<=n;i++)
	{
		int tmp=((long long)x*i*i+y*i+z)%20000;
		a[i]=tmp-10000;
	}
	b[1]=a[1];
	for(int i=2;i<=n+1;i++)
	{
		b[i]=min(b[i-1]+a[i],b[i-2]+a[i]);
	}
	cout<<b[n+1];
	
	
	return 0;
}