关注
楼主我又来啦,今晚又看了看这道题,用动态规划做了,感觉应该没啥问题,不知道能不能ac
#include<iostream>
(5488)#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int n;
cin>>n;
int k;
cin>>k;
vector<int> pos(n);
for(int i=0;i<n;i++){
cin>>pos[i];
}
//先对pos排序
sort(pos.begin(),pos.end());
int l=0,r=0;
vector<int> cover(n);
//双指针法,求出cover[0..n-1]
//cover[i]表示在pos中下标i之后(包括i)共有多少个馅饼与pos[i]的距离在k之内
//比如pos: 1 1 2 3 4 5 5
//如果k=1,则对应的cover: 3 2 2 2 3
while(l<n){
while(r<n&;&;pos[r]-pos[l]<=k){
++r;
}
cover[l]=(r-l);
++l;
}
/*
dp[i][j]表示: 必须恰好有j次选择了吃馅饼,
从pos中下标i开始选择吃或者不吃馅饼,
一直选到pos中的最后一个位置所能吃到的最多馅饼数量
*/
vector<vector<int>> dp(n);
for(int i=0;i<n;i++) {
dp[i].resize(3);
}
//必须选择吃2次馅饼,但此时只有最后一个馅饼,不符合题意,赋予-1方便后续比较
dp[n-1][2]=-1;
//必须选择吃1次馅饼,但此时只有最后一个馅饼,必须也只能选择吃它
dp[n-1][1]=1;
for(int i=n-2;i>=0;i--) {
for(int j=1;j<3;j++){
/*如果i+cover[i]==n并且必须恰好要有2次选择吃馅饼,
说明此时这个馅饼一定不能选择吃
否则的话,假如我们选择吃它,就会剩下一次必须选择吃馅饼的机会
但却没有馅饼可吃了,所以直接dp[i][j]=dp[i+1][j]*/
if(i+cover[i]==n&;&;j==2){
dp[i][j]=dp[i+1][j];
}
/*如果i+cover[i]==n并且必须恰好要有1次选择吃馅饼,
说明pos[i]这个馅饼一定要选择吃,因为这样会吃完pos[i]以及之后
的所有馅饼,一定是最多数量,直接dp[i][j]=cover[i]即可
*/
else if(i+cover[i]==n&;&;j==1){
dp[i][j]=cover[i];
}
/*如果i+cover[i]<n并且必须恰好要有1次选择吃馅饼(说明之前已经选择了一次,所以还剩下1次),
说明此时这个馅饼(pos[i])可以选择吃,也可以选择不吃,看哪个能吃饭的数量更多就选择哪个方案
*/
else if(i+cover[i]<n&;&;j==1){
dp[i][j]=max(cover[i],dp[i+1][j]);
}
/*如果i+cover[i]<n并且必须恰好要有2次选择吃馅饼(说明之前还没有一次选择吃馅饼,所以还剩下2次),
说明此时这个馅饼(pos[i])可以选择吃,也可以选择不吃,看哪个能吃饭的数量更多就选择哪个方案
*/
else if(i+cover[i]<n&;&;j==2){
dp[i][j]=max(dp[i+cover[i]][j-1]+cover[i],dp[i+1][j]);
}
}
}
// 从pos[0]开始决策,必须恰好只有2次选择吃馅饼的情况下所能吃到的最多数量即为答案
cout<<dp[0][2]<<endl;
return 0;
}
查看原帖
点赞 评论
相关推荐

点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 聊聊这家公司值得去吗 #
225738次浏览 2130人参与
# 硬件人你反向读研了吗 #
41633次浏览 629人参与
# 为了找工作你投递了多少公司? #
6616次浏览 84人参与
# 工作一周年分享 #
26644次浏览 126人参与
# 一人一个landing小技巧 #
77202次浏览 1106人参与
# kpi面有什么特征 #
28615次浏览 152人参与
# 入职第一天,你准备什么时候下班 #
54804次浏览 349人参与
# 小米提前批笔试难吗 #
33154次浏览 352人参与
# 正在实习的你,几点下班 #
156314次浏览 1085人参与
# 担心入职之后被发现很菜怎么办 #
125965次浏览 749人参与
# 一人推荐一个机械人值得去的公司 #
403222次浏览 4136人参与
# 毕业论文怎么查AI率 #
43047次浏览 1891人参与
# 夸夸我的求职搭子 #
192183次浏览 1898人参与
# 校招入职后的感受 #
274877次浏览 2668人参与
# 投格力的你,拿到offer了吗? #
82461次浏览 573人参与
# Tplink求职进展汇总 #
130312次浏览 728人参与
# 体制内上岸心路历程 #
26548次浏览 212人参与
# 华为池子有多大 #
87571次浏览 689人参与
# 产品每日一题 #
43540次浏览 563人参与
# tplink提前批进度交流 #
162345次浏览 1367人参与