一.动态规划
走楼梯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);
}
}
}
