题⽬8:Lazy Cow 懒惰的⽜
题⽬描述
这是⼀个炎热的夏⽇。懒洋洋的奶⽜⻉茜想将⾃⼰放置在⽥野中的某个位置, 以便可以在短距离内尽
可能多地吃到美味的草。⻉茜所在的⽥野中共有 N ⽚草 地,我们可以将⽥野视作⼀个⼀维数轴。 第 i
⽚草地中包含 gi 单位的⻘草,位置 坐标为 xi。不同草地的位置不同。⻉茜想选取⽥野中的某个点作为
她的初始位置(可 能是某⽚草地所在的点)。只有⼀⽚草地与她的初始位置的距离不超过 K 时,⻉ 茜
才能吃到那⽚草地上的草。
如果⻉茜选择最佳初始位置,请确定她可以吃到的⻘ 草最⼤数量。
![](https://profile-avatar.csdnimg.cn/f88d7d740b364e7ab4c540d97462a56b_weixin_53185809.jpg!4)
请问c++简单做法是什么
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- swadmin 2022-01-27 16:57关注
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<cstdio> using namespace std; struct lenka { long long x,y; }a[10000],b[10000]; int cmp(const lenka& x,const lenka& y) { if(x.y==y.y)return x.x<y.x; return x.y<y.y; } long long d[1001][1001][5]; int main() { int n,k,L; while(cin>>n>>k>>L) { for(int i=0;i<n;i++)scanf("%lld%lld",&a[i].x,&a[i].y); sort(a,a+n,cmp); int MAX=1; for(int i=0;i<n;) //把不同列的选出来 { if(i+1<n&&a[i+1].y==a[i].y)//找到同一列的 { b[MAX].x=a[i].y; b[MAX++].y=3; i+=2; } else { b[MAX].x=a[i].y; b[MAX++].y=a[i].x; i++; } // printf("第%lld列 %lld行\n",b[MAX-1].x,b[MAX-1].y); } memset(d,0x3f3f3f3f,sizeof d); d[0][0][3]=0; for(int i=1;i<MAX;i++) { for(int j=1;j<=k;j++) { long long A,B; A=min(min(d[i-1][j-1][1],d[i-1][j-1][2]),min(d[i-1][j-1][3],d[i-1][j-1][4])); if(j>=2)B=min(min(d[i-1][j-2][1],d[i-1][j-2][2]),min(d[i-1][j-2][3],d[i-1][j-2][4])); if(b[i].y==1) //只有第一行有牛 { d[i][j][1]=min(d[i][j][1],A+1); d[i][j][1]=min(d[i][j][1],d[i-1][j][1]+b[i].x-b[i-1].x);//延长之前的barn d[i][j][1]=min(d[i][j][1],d[i-1][j][4]+b[i].x-b[i-1].x); } else if(b[i].y==2) //只有第二行有牛 { d[i][j][2]=min(d[i][j][2],A+1); d[i][j][2]=min(d[i][j][2],d[i-1][j][2]+b[i].x-b[i-1].x); d[i][j][2]=min(d[i][j][2],d[i-1][j][4]+b[i].x-b[i-1].x); } d[i][j][3]=min(d[i][j][3],A+2); d[i][j][3]=min(d[i][j][3],d[i-1][j][3]+2ll*(b[i].x-b[i-1].x)); d[i][j][4]=min(min(d[i-1][j-1][1],d[i-1][j-1][2])+b[i].x-b[i-1].x+1,d[i-1][j][4]+2ll*(b[i].x-b[i-1].x)); if(j>=2)d[i][j][4]=min(d[i][j][4],B+2); } } cout<<min(min(d[MAX-1][k][1],d[MAX-1][k][2]),min(d[MAX-1][k][3],d[MAX-1][k][4]))<<endl; } return 0; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥200 csgo2的viewmatrix值是否还有别的获取方式
- ¥15 Stable Diffusion,用Ebsynth utility在视频选帧图重绘,第一步报错,蒙版和帧图没法生成,怎么处理啊
- ¥15 请把下列每一行代码完整地读懂并注释出来
- ¥15 pycharm运行main文件,显示没有conda环境
- ¥15 寻找公式识别开发,自动识别整页文档、图像公式的软件
- ¥15 为什么eclipse不能再下载了?
- ¥15 编辑cmake lists 明明写了project项目名,但是还是报错怎么回事
- ¥15 关于#计算机视觉#的问题:求一份高质量桥梁多病害数据集
- ¥15 特定网页无法访问,已排除网页问题
- ¥50 如何将脑的图像投影到颅骨上