一树状数组尾声仅一个题目树状数组求解最长上升子序列思路设置dp[i]维护以a[i]为结尾的最长上升子序列长度条件若有a[j] 满足(1)ji (2)a[j]a[i]则有dp[i]dp[j]1若保证dp[i]最大即在满足(1)(2)条件下使dp[j]最大求最大值的过程使用树状数组维护有函数ask(pos)查询值域 [1,pos]\内最大的 dp 值update(k,v)在值域 k 的位置更新保存更大的 dp 值 v这是整体思路详细解析在注释#includebits/stdc.h using namespace std; const int N1e65; int n,a[N],c[N],dp[N],ans; int lowbit(int n){ return n-n; } void update(int k,int v){ for(int ik;iN;ilowbit(i)){ c[i]max(c[i],v); } } int ask(int pos){ int ans0; for(int ipos;i;i-lowbit(i)){ ansmax(ans,c[i]); } return ans; } int main(){ scanf(%d,n); for(int i1;in;i){ scanf(%d,a[i]); a[i]; } //c[x] 维护值等于 x 的位置对应的最长上升子序列长度最大值 //更新条件(1)ij(2)a[i]a[j] for(int i1;in;i){ dp[i]ask(a[i]-1)1; //查询值域[1,a[i]-1](前缀)所有对应的dp值的最大值 //后面a[i1]到a[n]没update能保证位置ij(1) //值域到a[i]-1保证a[j]值一定小于当前位置值a[i](2)1即表示接上a[i] update(a[i],dp[i]); ansmax(ans,dp[i]);//所有位置最长上升子序列的最大值即为答案 } printf(%d\n,ans); }二拓扑排序适用于有向无环图 DAG若图有环则不存在拓扑序图中任意一条有向边 u to v顶点 u 在序列里一定出现在顶点 v 的前面 则这个序列就称为图 G 的拓扑序列求解该序列的过程叫做拓扑排序。求解过程就是先设置队列后遍历全图的点若该点入度为0入队后一直遍历队列出队直到队列为空遍历队列中点的临界点若其入度为0入队模板如下void kahn(){ queueint q; // 入度为0的点入队 for(int i1;in;i) if(in[i]0) q.push(i); while(!q.empty()){ int uq.front(); q.pop(); topo.push_back(u); for(int v:g[u]){ in[v]--; if(in[v]0) q.push(v); } } } main函数 for(int i1;im;i){ int u,v; cinuv; g[u].push_back(v); in[v] } kahn();例题解析食物链非常典型的模板如图所示为某生态系统的食物网示意图据图回答问题。现在给你n个物种和m条能量流动关系求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1 b1a2 b2a3 b3......am-1 bm-1am bm其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链我们分析题目食物网 有向无环图 DAG自然界不会出现捕食环不存在循环可以用拓扑排序 DP求解。设 dp[u]以 u 为终点的完整食物链数量。若 u 是生产者入度 0它自己不能算食物链但它是路径起点dp[u] 1代表一条待延伸的起始链若 u 不是生产者()所有有边的 v 的 dp 值相加。学过八下生物的都知道在计算食物链条数的时候若一点链接到该点该点的食物链数量可以继承那一个点的食物链数量若有多点则可全部继承进行累加我们再看第一个点生产者虽不算一条食物链但任意一点链接生产者都可以构成一条食物链根据上面的继承理论有dp[生产者]1输出方面只有出度 0的点才是食物链终点遍历所有点 u 如果 out[u] 0就把 dp[u] 累加到总答案里。 原因只有走到没有下一捕食者的生物才是一条完整食物链。代码如下#includebits/stdc.h const int N2e55; using namespace std; int n,m,in[N],out[N],dp[N],ans; vectorint g[N]; void tuopu(){ queueint q; for(int i1;in;i){ if(!in[i]out[i]) q.push(i),dp[i]1; } //dp[i]以i为终点的食物链条数 while(!q.empty()){ int uq.front(); q.pop(); for(int v:g[u]){ in[v]--; dp[v]dp[u]; if(!in[v]) q.push(v); } } } int main(){ scanf(%d%d,n,m); for(int i1;im;i){ int u,v; cinuv; g[u].push_back(v); in[v];out[u]; } tuopu(); for(int i1;in;i){ if(!out[i]) ansdp[i]; } coutans; }三并查集初步树形结构能够快速进行合并和查询的集合作用快速判断两点是否连通、合并连通块模板如下初始化 for(int i1;in;i){ fa[i]i; } 找祖先 int Find(int x){ if(xfa[x]) return x; return fa[x]Find(fa[x]); } 合并 void merge(int x,int y){ xFind(x),yFind(y); if(xy) return ; if(sz[x]sz[y]) swap(x,y); fa[x]y; sz[y]sz[x]; }今天到这