[OpenJudge8462][序列DP]大盗阿福
2024-09-01 17:11:47
大盗阿福
总时间限制: 1000ms 内存限制: 65536kB
[描述]
阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺,每家店中都有一些现金。阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。
作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?
输入输入的第一行是一个整数 T (T <= 50) ,表示一共有 T 组数据。
接下来的每组数据,第一行是一个整数 N (1 <= N <= 100, 000) ,表示一共有 N 家店铺。第二行是 N 个被空格分开的正整数,表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 1000 。输出对于每组数据,输出一行。该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。
[样例输入]
2
3
1 8 2
4
10 7 6 14
[样例输出]
8
24
[提示]
对于第一组样例,阿福选择第 2 家店铺行窃,获得的现金数量为 8 。
对于第二组样例,阿福选择第 1 和 4 家店铺行窃,获得的现金数量为 10 + 14 = 24 。
[Solution]
转移方程:dp[i]=max(dp[i-2]+data[i],dp[i-1])
#include <cstdio>
#include <algorithm>
using namespace std;
int T,N;
int data[],dp[];
int main(){
scanf("%d",&T);
for(int i=;i<=T;++i){
scanf("%d",&N); for(int j=;j<=N;++j) scanf("%d",&data[j]);
// dp[1]=data[1]; dp[2]=data[2];
for(int j=;j<=N;++j)
dp[j]=max(dp[j-]+data[j],dp[j-]);
printf("%d\n",dp[N]);
}
return ;
}
最新文章
- calculator
- JCreator的配置
- qq2440启动linux后插入u盘出现usb 1-1: device descriptor read/64, error -110,usb 1-1: device not accepting address 8, error -110
- c++builder调用VC的dll以及VC调用c++builder的dll
- BZOJ-3228 棋盘控制 线段树+扫描线+鬼畜毒瘤
- discuz安装与学习资料
- Jquery select 选中项中自定义的值
- poj2月下旬题解
- Ubuntu 12安装Virtualbox
- 笔记--cocos2d-x 3.0 环境搭建
- C语言常见错误笔记
- emacs Can&#39;t guess python-indent-offset, using defaults: 4
- C#语法快速热身
- mysql字符串查找(统计客源)
- python 三方面库整理
- github学习心得
- JavaScript(ES5)使用保留字作函数名
- JavaScript-isFinite()判断是否数字有效
- Logback 日志持久化
- easymock快速入门