黄冈市建设信息网站,郑州市建设工程信息网站,河池公司网站开发价格,齐齐哈尔市建设工程监察网站打家劫舍
题目难度#xff1a;高阶
时间限制#xff1a;1000ms
内存限制#xff1a;256mb
题目描述
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff…打家劫舍
题目难度高阶
时间限制1000ms
内存限制256mb
题目描述
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下能够偷窃到的最高金额。
输入格式
第一行一个整数n表示房屋的数量。
第二行n个整数空格隔开依次表示沿街n个房屋内的现金数量。
输出格式
一个整数表示小偷能得到的最高金额。
样例数据
输入样例
4
1 2 3 1输出样例
4数据范围
对100%的数据2n≤10^5每个房屋内金额不超过1000。 思路:
不要被这个高阶的难度吓到了其实很简单
首先我们知道这是动态规划所以定义一个数组long long dp[n10];
dp[i]代表从第一家一直偷到第i家最多能投到多少钱比如dp[5]表示从第一家到第五家最多偷几块钱
好的现在我们只要知道dp[i]等于什么就好了状态转移方程
分析一下假设我们知道了dp[1]到dp[4]的所有结果现在我们要求dp[5]应该怎么求呢
因为我们不能偷相邻的房间所以现在我们求dp[5]有两种选择
1、dp[5]dp[4]这是什么意思呢就是说我们从第一间房子偷到第四间房子已经偷了很多钱比如已经偷了114514元钱如果从第一间房子偷到第三间房子再偷第五间房子可能只能偷到1元这种时候最好的情况就是偷到第四间房子停下来不偷第五间了所以dp[5]只能等于偷到第四件的最大钱数
2、dp[5]dp[3]a[5]这又是什么意思呢就是从第一间房子偷到第三间房子再偷第五间房子这样偷到的钱可能会比偷到第四间房子偷的多所以我们就会选择能偷更多的2号方案就是从第一间房子偷到第三间房子再偷第五间房子
现在我们知道了已经有两种选择所以dp[i]max(dp[i-2]a[i],dp[i-1]);
现在我们还需要解决一个问题
如果dp[i]max(dp[i-2]a[i],dp[i-1]);那么当i3或者4时需要用到dp[1]或dp[2]但求dp[1]要求出dp[1-2]dp[-1],但我们不可能有dp[-1]这个数组所以dp[1]和dp[2]要我们提前求出来
dp[1]就等于第一间房子的钱数从第一间房子偷到第一间房子我们最多只能把第一间房子的钱全拿走
dp[2]max(a[1],a[2]);从第一间房子偷到第二间房子我们只能偷一间房子否则就会触发警报只能偷第一间或第二间
那么我们现在就能写出程序了 代码
#includebits/stdc.h
using namespace std;
int main(){long long n;cinn;long long a[n10],dp[n10];//a存每间房子的钱数 for(int i1;in;i){cina[i];//读入 }for(int i1;in;i){if(i1){//提前处理dp[1] dp[i]a[i];}else if(i2){//提前处理dp[2] dp[i]max(a[i-1],a[i]);}else{//否则就是正常状态了直接把状态转移方程抄进去 dp[i]max(dp[i-2]a[i],dp[i-1]);}}coutdp[n];//输出从第一间房子偷到第n间房子最多偷多少 return 0;
}
