动态规划之程序员的工作

vlambda
2020-06-09

动态规划之程序员的工作

题目

一个程序员每天上班后会收到当天的全部工作，每个程序由一个开始时刻与一个持续时间构成。

一个工作日为N分钟，从第一分钟开始到第N分钟结束。程序员到达单位后就开始工作。如果在同一时刻有多个程序需要完成，他可以任选其中的一个来做，而其余的则由他的同事完成，反之如果只有一个程序，则该程序必需由他去写成，假如某些程序开始时刻他正在工作，则这些程序也由他的同事完成。如果某程序于第P分钟开始，持续时间为T分钟，则该程序将在第P+T-1分钟结束。

写一个程序计算该工作人员应该如何选取程序，才能获得最大的空暇时间。

解析

这道题因为容易出现重复

所以一般使用倒推的方法

首先我亲爱的达瓦里氏们

我们需要确定边界

因为是倒推

我们要将a[n+1]赋值为0

下面就要开始倒推

倒推时

分为两种情况

一种是

没有任务从此时开始

这样很简单

这一分钟时的休息时间

等于a[i+1]+1

第二种是

有任务从此时开始

那就要选择所有数值中最大的

最终

a[1]为正确答案

加油！

大家最爱的代码

#include<bits/stdc++.h>

#include<iostream>

#include<cstdlib>

#include<cstdio>

using namespace std;

int main()

{

int n,k,a[1001],b[1001],c[1001],maxx=0;

bool flag=true;

cin>>n>>k;

memset(c,0,sizeof(c));

for(int i=1;i<=k;i++)

cin>>a[i]>>b[i];

for(int i=n;i>=1;i--)

{

flag=true;

maxx=0;

for(int j=k;j>=1;j--)

{

if(a[j]==i)

{

if((a[j]+b[j])>maxx)

{

maxx=a[j]+b[j];

flag=false;

}

if(flag==true)

c[i]=c[i+1]+1;

else

c[i]=c[maxx];

}

//for(int i=1;i<=n;i++)

//cout<<c[i]<<" ";

//cout<<endl;

cout<<c[1]<<endl;

return 0;

}

拜拜！！！

加油！

动态规划之程序员的工作

出gai 动态规划之程序员的工作

加油

往期精彩推荐

本文合肥一六八中学校园图片

来自老爸学校的张尚镯伯伯

在此表示感谢动态规划之程序员的工作

欢迎关注

亮星的信息学小屋

觉得有用，请点右下方“在看”，谢谢鼓励

vlambda博客
学习文章列表