【t046】牛跳
2024-09-06 14:13:40
Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
John的奶牛们计划要跳到月亮上去。它们请魔法师配制了P(1 <= P <=150,000)种药水,这些药水必需安原来的先后次序使用,
但中间可以跳过一些药水不吃。每种药水有一个“强度”值 s ( 1 <= s <= 500 ),表示可以增强牛的跳跃能力。然而,药力的
作用却是交替相反方向起作用,也就是说:当第奇数次吃药时,牛获得跳的更高的能力,而第偶数吃药时,却降低了跳高能力
。在吃药前,牛的跳高能力当然为 0 。
每种药只能吃一次,开始时为第1次吃药。
请求出牛可能跳到的最高高度--最大跳跃能力。
【输入格式】
第一行:一个整数 P
下面P行:每行一个整数,表示按先后次序要吃的药水的“强度”。
【输出格式】
只一个整数,表示最大弹跳能力。
去掉第2、4两种药水,
样例处理方式:
吃药为:
7,1,8,3,6;
最终能力为:
7-1+8-3+6=17
Sample Input
8
7
2
1
8
4
3
5
6
Sample Output
17
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t046
【题意】
【题解】
设fij表示前i个药水中选择了奇偶性为j的个数的药的最大跳跃值。
0和1分别表示偶数和奇数
对于第i个药水,有选择它和不选两种结果。
选它的话,和前i-1个的奇偶性不同,不选它的,则一样。
//选
f[i][0] = f[i-1][1]-a[i];
f[i][1] = f[i-1][0]+a[i];
//不选
f[i][0] = max(f[i][0],f[i-1][0]);
f[i][1] = max(f[i][1],f[i-1][1]);
//边界
f[1][0] = 0;//表示不选第一个
f[1][1] = h[1];//选第一个,变成奇数
搞出奇偶性为奇数和偶数的最大值就好。
第i个选择完之后,它选与不选只会对前i个造成影响。只要他做出了正确的选择,对后续就不会产生影响。
【完整代码】
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 15e4+100;
int n;
int a[N],f[N][2];
void in()
{
rei(n);
rep1(i,1,n)
rei(a[i]);
}
void do_dp()
{
f[1][0] = 0;
f[1][1] = a[1];
rep1(i,2,n)
{
//选
f[i][0] = f[i-1][1]-a[i];
f[i][1] = f[i-1][0]+a[i];
//不选
f[i][0] = max(f[i][0],f[i-1][0]);
f[i][1] = max(f[i][1],f[i-1][1]);
}
}
void o()
{
printf("%d\n",max(f[n][0],f[n][1]));
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
in();
do_dp();
o();
return 0;
}
最新文章
- 【好文要转】HTTP图解(大牛必经之路)
- bzoj 1030 fail树dp
- iOS开发之总结
- ES5中的有9个Array方法
- mybatis系列-11-一对多查询
- ios开发——实用技术篇Swift&;Swift调用C、C++、Object
- 云平台编程与开发(七)-使用X5Cloud云平台开发网络彩讯
- 跟我一起学PCL打印语言(一)
- CouldnotcreateServerSocketonaddress0.0.0.0/0.0.0.0:9083
- vim netrw
- HDU 2504 又见GCD
- iOS代码处理横屏问题
- linux脚本定时备份数据库表(详解)
- 爬取西刺网代理ip,并把其存放mysql数据库
- 测试同学难道要写一辈子的hello world?
- Linux下面如何用tcpdump抓包
- 小程序实现GBK编码数据转为Unicode/UTF8
- Linux ACL 权限
- ssh连接虚拟机centos
- python第二十四天-----作业终于完成啦