【Gym 100733D】Little thief Shi(取数,DP)
Shi realized that he was almost out of money, even renting Shitalian lands. Shi was walking on a street, while thinking of a way to recover his fortune. In his way, he passed by a jewelry store. The owner of the store was a Shitalian man suspected of committing minor crimes, as cutting bushes and stealing old bread. Shi hated people who cut bushes, so he decided to rob the store to take revenge and make some money.
The store has n jewels, put in a row, one after another. Each jewel i can be sold in the black market for a value vi. Shi wants to steal as much as possible, but if he steals everything, the owner will notice, so if Shi steals the i-th jewel, he can't steal the i - 1-th, i - 2-th, i + 1-th and i + 2-th jewels.
Using the best strategy possible, calculate the sum of the jewels values that Shi can obtain.
The input begins with an integer n (1 ≤ n ≤ 106), indicating the number of jewels in the store. The next line containsn integers. The i-th integer vi (1 ≤ vi ≤ 103) is the value of the i-th jewel.
Output the maximum value that Shi can get.
4
1 2 3 4
5
6
1 2 4 0 3 0
5
7
2 10 12 24 29 69 0
81
10
15 1 6 3 7 100 9 15 80 95
210
题意:n个数字,每次最少隔两个取一个,求取得数的最大和
分析:dp,想法一、s[i]表示取第i个时最大和为多少,那就取不了i-1、i-2,可以取i-3、i-4、i-5,.....,当取i-6时,可取i-3,显然取了更划算,同理,i-7、i-8在算s[i-4]、s[i-5]时考虑过了,s[i]=a[i]+max{s[i-3],s[i-4],s[i-5]}
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,s[],tem,ans=;
int main(){
scanf("%d",&n);
for(int i=;i<n+;i++)
{
scanf("%d",&tem);
s[i]=max(s[i-],max(s[i-],s[i-]))+tem;
ans=max(ans,s[i]);
}
printf("%d",ans);
return ;
}
想法二、也是dp,s[i]表示前i个的最大和为多少,s[i]=max{s[i-1],s[i-3]+第i个}
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,s[],tem;
int main(){
scanf("%d",&n);
for(int i=;i<n+;i++)
scanf("%d",&tem),s[i]=max(s[i-],tem+s[i-]);
printf("%d",s[n+]);
return ;
}
最新文章
- deepsooncms在Ubuntu 14.04上部署教程
- AngularJS 系列 02 - 模块
- bzoj1835[ZJOI2010]base基站选址
- css——手机端图片正确显示
- SpringMVC+Spring+MyBatis整合完整版Web实例(附数据)
- Linux文件描述符与打开文件之间的区别(转载)
- asp.net跨页面传值
- 使用AmplifyJS和JQuery编写更好更优雅的javascript事件处理代码
- 李洪强iOS开发之-环信04_消息
- [置顶] Android开发之serviceManager分析
- Android(digest)
- vsftp实现只能上传不能下载、删除权限配置
- mac 系统安装 eclipse 方法
- GraphQL
- OI养老专题03:让坏人出列的约瑟夫问题
- 【C语言 基础】什么流程控制?
- iOS之Safari调试webView/H5页面
- 微擎开发------day01
- python 数字
- Notes on Large-scale Video Classification with Convolutional Neural Networks