关注
楼主我又来啦,今晚又看了看这道题,用动态规划做了,感觉应该没啥问题,不知道能不能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;
}
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享

点赞 评论 收藏
分享
05-12 17:00
门头沟学院 Java 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 聊聊这家公司值得去吗 #
232831次浏览 2182人参与
# kpi面有什么特征 #
31597次浏览 202人参与
# 你认为哪个岗位找工作最卷 #
12262次浏览 41人参与
# 职场人,说说你的烦心事 #
8497次浏览 71人参与
# 一人一个landing小技巧 #
78966次浏览 1123人参与
# 职场上哪些事情令人讨厌 #
16638次浏览 82人参与
# 秋招最大的收获是什么? #
33839次浏览 296人参与
# 小红书求职进展汇总 #
56067次浏览 485人参与
# 聊聊你的职场新体验 #
157400次浏览 1369人参与
# 机械制造岗投递时间线 #
22707次浏览 346人参与
# 职场吐槽大会 #
205314次浏览 1635人参与
# 研究所VS国企,该如何选 #
180558次浏览 1769人参与
# 为了找工作你投递了多少公司? #
9372次浏览 127人参与
# 大家每天通勤多久? #
41948次浏览 329人参与
# 通信硬件牛牛的实习日记 #
7143次浏览 65人参与
# 职场破防瞬间 #
234886次浏览 2125人参与
# 总结:哪家公司面试体验感最好 #
47600次浏览 336人参与
# tplink提前批进度交流 #
162702次浏览 1378人参与
# 找工作前vs找工作后的心路变化 #
9569次浏览 102人参与
# 担心入职之后被发现很菜怎么办 #
126303次浏览 754人参与