ennn,今天是0x125E591的生日 大家+1s.-xcc
T1:LG奇怪的电梯.
S1:对每一个点建合法的边,跑最短路.(ps:因为不是DP,不上码了.)
T2:LG尼克的任务.
S2:遗憾考试卡在这个题上,最后连暴力都没打.看到给定一段段区间关联交并问题,自然地联想到了昨天做LG上的饥饿的奶牛 ,于是设了f[ i ][ 0/1]表示为第 i 段选或不选并保证前 i 段都会合法覆盖的情况下最少工作时间,f[ i ][ 0 ]则枚举i之前的区间k能覆盖i区间的进行f[ i ][ 0 ]=max{f[k][1]}的转移,f[ i ][ 1 ]则变得不好处理,要去找不覆盖i区间的区间k,并找到最小代价v将Σk覆盖,f[ i ][1]=max(f[ i ][ 1],v+time[i]),最后发现v怎么也找不出来,并发现后面的选择还会影响前面的状态,这样推dp显然是不行的.看了题解,发现果然要倒推,因为后面的状态影响前面的状态.记录此时不是任务开头,就f[ i ]=f[ i+1]+1,有任务就执行,f[ i ]=Σmax(f[ i ],f[ i+len]),建议调试样例,自然会懂.
总结:①平静下来,不会正解打暴力.②MS:code once,think twice.
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define R register int n,k,id=1,sum[10010],f[10010]; struct bian{ int L,v; }len[10010]; bool cmp(bian a,bian b){return a.L>b.L;} int main() { freopen("LIGNJA.in","r",stdin); freopen("LIGNJA.out","w",stdout); scanf("%d%d",&n,&k); for(R int i=1;i<=k;++i){ scanf("%d%d",&len[i].L,&len[i].v); ++sum[len[i].L]; } sort(len+1,len+1+k,cmp); for(R int i=n;i>=1;--i){ if(!sum[i]) f[i]=f[i+1]+1; else{ for(R int j=1;j<=sum[i];++j){ f[i]=max(f[i],f[i+len[id].v]); ++id; } } } printf("%d",f[1]); }
T5:LGP1233
S5:不知道为什么考试脑抽,对于双要求的最长不下降子序列,自己就将两个要求一起判断求???其实要联想到LG友好城市.将一个要求sort确定下来,另一个在此基础上求.
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define R register int n,q[5010],lenth; struct bian{ int L,W; }len[5010]; bool cmp(bian a,bian b){ if(a.L==b.L) return a.W<=b.W; else return a.L<b.L; } int find(int x) { int l=1,r=lenth; while(l<r){ int mid=(l+r)>>1; if(q[mid]<=x) r=mid; else l=mid+1; } return l; } int main() { freopen("STICK.in","r",stdin); freopen("STICK.out","w",stdout); scanf("%d",&n); for(R int i=1;i<=n;++i) scanf("%d%d",&len[i].L,&len[i].W); sort(len+1,len+1+n,cmp); q[++lenth]=len[1].W; for(R int i=2;i<=n;++i) { if(len[i].W<q[lenth]) q[++lenth]=len[i].W; else if(len[i].W>=q[lenth]){ int id=find(len[i].W); q[id]=len[i].W; } } printf("%d",lenth); return 0; }
PS:①:当一个元素一个标志相同时,另一个标志小sort时放前,这样单调栈求最长下降子序列时长度会往小的方面发展.
②:二分查找找维护单调下降的序列中第一个比它小的是这样写,其他要求跟题目意思来,注意等号给左边给右边关系"比它小比它大问题".
T3,T4有时间再补.
原文:https://www.cnblogs.com/xqysckt/p/11370152.html