week13周报

一.动态规划

1. 走楼梯2

难点：不能连续走三次两级台阶如何表示

思路：可以用二维数组f[i][j],i表示当前台阶数，j表示已经连续走了j次二级台阶了

转移方程：f[i+2][j+1]=f[i+2][j+1]+f[i][j] 当j！=2时，我们可以选择走二级台阶

f[i+1][0]=f[i+1][0]+f[i][j] 选择走一级台阶，此时j变为了0

这两种情况是同时进行的

代码：

#include <bits/stdc++.h>

using namespace std;

int main()

{

int n;

cin>>n;

long long f[55][5];

memset(f,0,sizeof(f));

f[0][0]=1;

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

{

for(int j=0;j<=2;j=j+1)

{

if(j!=2)

{

f[i+2][j+1]=f[i+2][j+1]+f[i][j];

}

f[i+1][0]=f[i+1][0]+f[i][j];

}

}

long long sum=f[n][0]+f[n][1]+f[n][2];

cout<<sum;

return 0;

}

2.任务分配

难点：是以时刻来枚举还是任务编号来枚举

思路：本题以时刻来枚举，可以通过起始时间和结束时间来进行转移

转移方程：

f[g[num].e]=max(f[g[num].e],f[i]+g[num].w);当此时刻i与当前任务的起始时间相等时，我们可以选择做此任务

f[i+1]=max(f[i],f[i+1]);此时刻不选择做任务或者无任务可做

两个方程同时进行

代码：

#include <bits/stdc++.h>

using namespace std;

struct ren

{

int s;

int e;

int w;

}g[1005];

bool cmp (ren a,ren b)

{

return (a.s<b.s||a.s==b.s&&a.e<b.e);

}

int f[1006];

int main()

{

int n;

cin>>n;

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

{

cin>>g[i].s>>g[i].e>>g[i].w;

}

sort(g+1,g+n+1,cmp);

int num=1;

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

{

while(i==g[num].s)

{

f[g[num].e]=max(f[g[num].e],f[i]+g[num].w);

num=num+1;

}

f[i+1]=max(f[i],f[i+1]);

}

cout<<f[1005];

}

3.走路（此题略过，思路和前面两题类似）

二.二分查找

1.饿饿 饭饭

难点：如何分辨题目为二分答案类型题

思路：由于此题数据极大，普通的枚举一定过不了，需要一个快速的方法把前面的绝大部分流程跳过，因此我们用到了二分答案

二分答案的操作：寻找打到了mid轮之后，再打一轮就会超过总数k。判断条件：第mid轮打的total份饭<=总数k

代码：

#include <bits/stdc++.h>

using namespace std;

long long a[100050],c[100050];

int n;

long long k;

long long check(int x)

{

long long tt=0;

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

{

if(a[i]<=x)

{

tt=tt+a[i];

}

else

{

tt=tt+x;

}

}

return tt;

}

int main()

{

cin>>n>>k;

long long zong=0;

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

{

cin>>a[i];

zong=zong+a[i];

}

if(zong<k)

{

cout<<"-1";

}

else if(zong==k)

{

return 0;

}

else

{

int l=0;

int r=1e9;

while(l+1<r)

{

int mid=(l+r)/2;

if(check(mid)>k)

{

r=mid;

}

else

{

l=mid;

}

}

k=k-check(l);

int tot=0;

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

{

if(a[i]>l)

{

c[++tot]=i;

}

}

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

{

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

}

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

{

if(a[c[i]]!=l+1)

{

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

}

}

}

}

三.set的用法

1.订单编号

知识点：set容器其中的元素会自动排好队，并且不允许有重复元素

set的各常用成员函数列表:

insert()–在集合中插入元素

begin()–返回指向第一个元素的迭代器

end()–返回指向最后一个元素下一个位置（注意不是最后一个元素）的迭代器

clear()–清除所有元素

count()–返回某个值元素的个数

empty()–如果集合为空，返回true

find()–返回一个指向被查找到元素的迭代器

size()–集合中元素的数目

swap()–交换两个集合变量

upper_bound()–返回大于某个值元素的迭代器

lower_bound()--饭后第一个大于某个值元素的元素位置

max_size()–返回集合能容纳的元素的最大限值

rbegin()–返回指向集合中最后一个元素的反向迭代器

rend()–返回指向集合中第一个元素的反向迭代器

erase(itr)-删除整个已存在的容器

难点：此题需要返回未出现过的比原先值大的第一个数，这需要枚举很多内容，极有可能出现time limited这一错误信息

思路：set函数中的lower_bound()函数可以直接返回第一个大于元素的位置，可以用set存储

另外，我们可以用分区间的做法，来把已选值剔除出我们的枚举区间

另另外，这题思路好难，我尽力了

代码：

#include <bits/stdc++.h>

using namespace std;

int n;

set<pair<int,int> > c;

inline void insert(int l,int r)//往insert()函数中内置代码

{

if(l>r)

{

return;

}

c.insert(make_pair(r,l));

}

int main()

{

cin>>n;

c.insert(make_pair(2e9,1));

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

{

int x;

cin>>x;

auto itr=c.lower_bound(make_pair(x,0));

if(itr->second<=x)//分区间做法

{

cout<<x<<" ";

insert(itr->second,x-1);

insert(x+1,itr->first);

c.erase(itr);

}

else

{

cout<<itr->second<<" ";

insert(itr->second+1,itr->first);

c.erase(itr);

}

}

}