题解 | #打家劫舍(二)# 活用容器

打家劫舍(二)

https://www.nowcoder.com/practice/6a8b2ceb3f8f4e5891939d7d7cbbd2c4

经典问题很多书上都有,比起通常解法用了std的deque容器,可以更方便地操作头尾,不用处理麻烦的下标。

#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int calc(vector<int>& dp,deque<int>& houses){
    int i;
    dp[0]=houses[0];
    dp[1]=houses[1];
    for(i=2;i<dp.size();++i){
        dp[i]=max(dp[i-1],dp[i-2]+houses[i]);
    }

    return dp[dp.size()-1];
}
int main() {
    int n,t,result1,result2;
    cin>>n;
    deque<int> houses;
    vector<int> dp(n-1);
    while(--n){
        cin>>t;
        houses.push_back(t);
    }
    result1=calc(dp,houses);
    cin>>t;
    houses.push_back(t);
    houses.pop_front();
    result2=calc(dp,houses);
    cout<<max(result1,result2)<<endl;

}
// 64 位输出请用 printf("%lld")

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-23 14:13
这是聊岔撇了吗,相同的话问了两遍
吴offer选手:上下文切换这一块
点赞 评论 收藏
分享
07-10 14:08
已编辑
江西农业大学 Java
拒绝无效加班的小学生...:期望3k吗?java这辈子有了
点赞 评论 收藏
分享
机械打工仔:有说的你怀疑一下就行了,直接问也太实诚了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务