苏州外贸公司网站建设流程图,浙江省建设厅查询官方网站,360搜索引擎地址,wordpress 内链引用一.动态规划走楼梯2难点#xff1a;不能连续走三次两级台阶如何表示思路#xff1a;可以用二维数组f[i][j],i表示当前台阶数#xff0c;j表示已经连续走了j次二级台阶了转移方程#xff1a;f[i2][j1]f[i2][j1]f[i][j] 当j#xff01;2时#xff0c;我们可以选择走二级台阶…一.动态规划走楼梯2难点不能连续走三次两级台阶如何表示思路可以用二维数组f[i][j],i表示当前台阶数j表示已经连续走了j次二级台阶了转移方程f[i2][j1]f[i2][j1]f[i][j] 当j2时我们可以选择走二级台阶 f[i1][0]f[i1][0]f[i][j] 选择走一级台阶此时j变为了0 这两种情况是同时进行的代码#include bits/stdc.husing namespace std;int main(){int n;cinn;long long f[55][5];memset(f,0,sizeof(f));f[0][0]1;for(int i0;in;ii1){for(int j0;j2;jj1){if(j!2){f[i2][j1]f[i2][j1]f[i][j];}f[i1][0]f[i1][0]f[i][j];}}long long sumf[n][0]f[n][1]f[n][2];coutsum;return 0;}2.任务分配难点是以时刻来枚举还是任务编号来枚举思路本题以时刻来枚举可以通过起始时间和结束时间来进行转移转移方程f[g[num].e]max(f[g[num].e],f[i]g[num].w);当此时刻i与当前任务的起始时间相等时我们可以选择做此任务f[i1]max(f[i],f[i1]);此时刻不选择做任务或者无任务可做两个方程同时进行代码#include bits/stdc.husing namespace std;struct ren{int s;int e;int w;}g[1005];bool cmp (ren a,ren b){return (a.sb.s||a.sb.sa.eb.e);}int f[1006];int main(){int n;cinn;for(int i1;in;ii1){cing[i].sg[i].eg[i].w;}sort(g1,gn1,cmp);int num1;for(int i1;i1005;ii1){while(ig[num].s){f[g[num].e]max(f[g[num].e],f[i]g[num].w);numnum1;}f[i1]max(f[i],f[i1]);}coutf[1005];}3.走路此题略过思路和前面两题类似二.二分查找1.饿饿 饭饭难点如何分辨题目为二分答案类型题思路由于此题数据极大普通的枚举一定过不了需要一个快速的方法把前面的绝大部分流程跳过因此我们用到了二分答案二分答案的操作寻找打到了mid轮之后再打一轮就会超过总数k。判断条件第mid轮打的total份饭总数k代码#include bits/stdc.husing namespace std;long long a[100050],c[100050];int n;long long k;long long check(int x){long long tt0;for(int i1;in;ii1){if(a[i]x){tttta[i];}else{ttttx;}}return tt;}int main(){cinnk;long long zong0;for(int i1;in;ii1){cina[i];zongzonga[i];}if(zongk){cout-1;}else if(zongk){return 0;}else{int l0;int r1e9;while(l1r){int mid(lr)/2;if(check(mid)k){rmid;}else{lmid;}}kk-check(l);int tot0;for(int i1;in;ii1){if(a[i]l){c[tot]i;}}for(int ik1;itot;ii1){coutc[i] ;}for(int i1;ik;ii1){if(a[c[i]]!l1){coutc[i] ;}}}}三.set的用法1.订单编号知识点set容器其中的元素会自动排好队并且不允许有重复元素set的各常用成员函数列表:insert()–在集合中插入元素begin()–返回指向第一个元素的迭代器end()–返回指向最后一个元素下一个位置注意不是最后一个元素的迭代器clear()–清除所有元素count()–返回某个值元素的个数empty()–如果集合为空返回truefind()–返回一个指向被查找到元素的迭代器size()–集合中元素的数目swap()–交换两个集合变量upper_bound()–返回大于某个值元素的迭代器lower_bound()--饭后第一个大于某个值元素的元素位置max_size()–返回集合能容纳的元素的最大限值rbegin()–返回指向集合中最后一个元素的反向迭代器rend()–返回指向集合中第一个元素的反向迭代器erase(itr)-删除整个已存在的容器难点此题需要返回未出现过的比原先值大的第一个数这需要枚举很多内容极有可能出现time limited这一错误信息思路set函数中的lower_bound()函数可以直接返回第一个大于元素的位置可以用set存储另外我们可以用分区间的做法来把已选值剔除出我们的枚举区间另另外这题思路好难我尽力了代码#include bits/stdc.husing namespace std;int n;setpairint,int c;inline void insert(int l,int r)//往insert()函数中内置代码{if(lr){return;}c.insert(make_pair(r,l));}int main(){cinn;c.insert(make_pair(2e9,1));for(int i1;in;ii1){int x;cinx;auto itrc.lower_bound(make_pair(x,0));if(itr-secondx)//分区间做法{coutx ;insert(itr-second,x-1);insert(x1,itr-first);c.erase(itr);}else{coutitr-second ;insert(itr-second1,itr-first);c.erase(itr);}}}
