广西翔路建设有限责任公司网站,网站建设市场占有率,免费学习的网站平台,重庆seo海洋qq1301#xff1a;大盗阿福 时间限制: 1000 ms 内存限制: 65536 KB 提交数:13109 通过数: 6123
【题目描述】 阿福是一名经验丰富的大盗。趁着月黑风高#xff0c;阿福打算今晚洗劫一条街上的店铺。 这条街上一共有 N#xfffd; 家店铺#xff0c;每家店中都有一…1301大盗阿福 时间限制: 1000 ms 内存限制: 65536 KB 提交数:13109 通过数: 6123
【题目描述】 阿福是一名经验丰富的大盗。趁着月黑风高阿福打算今晚洗劫一条街上的店铺。 这条街上一共有 N 家店铺每家店中都有一些现金。阿福事先调查得知只有当他同时洗劫了两家相邻的店铺时街上的报警系统才会启动然后警察就会蜂拥而至。 作为一向谨慎作案的大盗阿福不愿意冒着被警察追捕的风险行窃。他想知道在不惊动警察的情况下他今晚最多可以得到多少现金 【输入】 输入的第一行是一个整数T(T≤50)(≤50) 表示一共有T组数据。 接下来的每组数据第一行是一个整数N(1≤N≤100,000)(1≤≤100,000) 表示一共有N家店铺。第二行是N个被空格分开的正整数表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过10001000。 【输出】 对于每组数据输出一行。该行包含一个整数表示阿福在不惊动警察的情况下可以得到的现金数量。 【输入样例】
2
3
1 8 2
4
10 7 6 14
【输出样例】
8
24
【提示】 对于第一组样例阿福选择第22家店铺行窃获得的现金数量为88。 对于第二组样例阿福选择第11和44家店铺行窃获得的现金数量为101424101424。 解题思路 关键是找到这题的递推方程ansmaxdfsx2a[x]dfsx1要么洗劫这家然后考虑间隔的下家要么洗劫下家。然后再记忆化搜索不然会超时。 #includeiostream
#includecstring
#includecmath
#includealgorithm
#includestring
#includevector
#includemath.h
#includeiomanip
#includeset
#includequeue
#includestack
#includemap
#includelist
#include stdlib.h
#includedeque
using namespace std;
int n, t, a[100005],ans,b[100005];//a是存每家店的现金b是存洗劫前i家的最大收益
int dfs(int x)
{if (x n){return 0;}else if (b[x] ! 0){return b[x];}else{b[x] max(dfs(x 1), (dfs(x 2) a[x]));//把考虑到第i家前的情况全部存起来免得再花大量时间去搜return b[x];}
}
int main()
{cin t;while (t--){cin n;for (int i 1; i n; i){cin a[i];}ansdfs(1);cout ans endl;memset(b, 0, sizeof(b));}
}
