这题之前写过，记得当时蠢萌地敲了一个很复杂的循环，并且把答案存了下来，现在想想，当时真是有毅力。
由于题目输出数据不超过 40KB ，算一下也就只有 40960 个字符，所以不用害怕超时，我们只要递归跑一下就好了。定义 solve(intL,intR,intp) 表示解压 p 次[L,R]，然后扫 p 次，每次从L扫到 R ：当遇到数字num时，我们记当前位置为 pos ，那么括号里的内容则为 [pos+2,nxt[pos+1]−1] （其中 nxt[i] 表示 i 为“(”时对应 ")" 的位置），所以我们执行 solve(pos+2,nxt[pos+1]−1,num) ，即解压这段区间 num 次，最后我们要跳过这段区间，直接到 ")" 的右边；当遇到其他字符时直接输出即可。这样代码极短，空间也极小。
char s[M]; int nxt[M],stk[M],top; void solve(int L,int R,int p){ for(int i=1;i<=p;i++) for(int j=L;j<=R;j++) if(s[j]>='2'&&s[j]<='9'){ int num=s[j]-'0'; solve(j+2,nxt[j+1]-1,num); j=nxt[j+1]; }else putchar(s[j]); } int main(){ scanf("%s",s+1); int n=strlen(s+1); for(int i=1;i<=n;i++) if(s[i]=='(')stk[++top]=i; else if(s[i]==')')nxt[stk[top--]]=i; solve(1,n,1); putchar('\n'); return 0; }考试的时候我只写了60分这档的，暴力 O(n∗m2)的dp 。为了弄明白 dp 是如何一步一步优化，我尝试了从60分优化到80分，再从80分优化到100分，这是一种很好理解和掌握 dp 优化的方法。下面我把三档的做法都讲一下，并简单地写一写想到优化方法的思路。
60分：我们很容易得出这是一道 dp 题（因为我简单地想了想贪心之类的算法，发现很难找到答案），既然是 dp 题，那最重要的就是状态的定义了，其次是状态转移。对于每次转移，我们要从之前的状态里得出结果，因此我们需要一种状态来表示当前位置的最优解，又能便于后面的状态转移。对于一个点能否被染色，我们需要看它前两个点，它与前面第二个点的距离必须小于等于 m ，因此我们定义的状态一定要存下两个点位置（最后一个点和倒数第二个点）。有些同学没有经过思考，直接定义了一个n∗n的数组，这显然浪费了很多空间，因为倒数第二个点最多只有 m−1 个（它离最后一个点的距离不能超过 m−1 ），所以只要 n∗m 的数组就够了，存一下倒数第二个点离最后一个点的距离。于是就有了 dp[i][j] ，表示最后一个点为 i ，倒数第二个点离最后一个点的距离为j时的最小花费。 刷表、填表都一样，反正都是 O(n∗m2) 的。我用的是刷表法，因为感觉这样好写点。
void check(int &a,int b){ if(a==-1||a>b)a=b; } int n,m; int A[M]; int dp[505][105];//最后染i,前一个距离i为j int main(){ Rd(n);Rd(m); for(int i=1;i<=n;i++)Rd(A[i]); memset(dp,-1,sizeof(dp)); int ans=-1; for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++) dp[j][j-i]=A[i]+A[j]; for(int i=1;i<=n;i++) for(int j=1;j<m;j++) if(~dp[i][j]){ if(i-j>n-m)check(ans,dp[i][j]); for(int k=i+1;k<=i-j+m;k++)//i-j+m check(dp[k][k-i],dp[i][j]+A[k]); } Pt(ans); putchar('\n'); return 0; }80分：假如用上述60分的代码来写80分的话，空间并不会超，而时间大大超过了限制，因此我们要优化时间。 dp 优化时间的出发点一般是减少状态转移复杂度，我们可以先往这方面想，所以必须要用填表，因为这样才可以从前面转移过来一个最优解。我们每次枚举最后一个染色位置 i 和它与倒数第二个染色位置的距离j，说明我们已经知道了两个点的位置，所以这个状态能影响的区间是固定的，我们只需要从前面找一个最优解即可，这样后面的状态从这个状态转移来的一定是最优解。我们可以用优先队列 quei 来维护最小值（ quei 表示最后一个点为 i 时的优先队列），然后在每次转移时从枚举的倒数第二个点的优先队列中求答案就行了。
typedef pair<int,int> P; int n,m; struct node{ P num[1005]; int L,R; void push(P x){ while(L<R&&num[R-1].first>x.first)R--; num[R ]=x; } P top(int x){ while(L<R&&x-num[L].second>m)L ; return num[L]; } node(){L=0;R=0;} }que[10005]; void check(int &a,int b){ if(a==-1||a>b)a=b; } int A[N]; int dp[10005][1005]; int main(){ Rd(n);Rd(m); for(int i=1;i<=n;i )Rd(A[i]); for(int i=1;i<=m;i ) for(int j=i 1;j<=m;j ){ dp[j][j-i]=A[i] A[j]; que[j].push(P(dp[j][j-i],i)); } int ans=-1; for(int i=m 1;i<=n;i ) for(int j=m-1;j>=1;j--){ int t=i-j; P q=que[t].top(i); dp[i][j]=q.first A[i]; if(t>n-m)check(ans,dp[i][j]); que[i].push(P(dp[i][j],t)); } Pt(ans); putchar('\n'); return 0; }100分：其实80分的时间复杂度已经够100分的数据跑了，只是空间会超，对于dp的空间优化，最简单的就是用滚动数组了，因为我们转移时只需要用到之前 m 次的dp值，所以我们只要把 dp 开成 m∗m 的就行了，第一维 modm 滚动。
int n,m; struct node{ P num[1005]; int L,R; void push(P x){ while(L<R&&num[R-1].first>x.first)R--; num[R++]=x; } P top(int x){ while(L<R&&x-num[L].second>m)L++; return num[L]; } void clear(){ L=R=0; } node(){L=R=0;} }que[M]; void check(int &a,int b){ if(a==-1||a>b)a=b; } int A[N]; int mod[N]; int dp[M][M]; int main(){ Rd(n);Rd(m); for(int i=1;i<=n;i++)Rd(A[i]); for(int i=1;i<=n;i++)mod[i]=i%m; for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++){ dp[mod[j]][j-i]=A[i]+A[j]; que[mod[j]].push(P(dp[mod[j]][j-i],i)); } int ans=-1; for(int i=m+1;i<=n;i++){ int cur=mod[i]; que[cur].clear(); for(int j=m-1;j>=1;j--){ int t=i-j; P q=que[mod[t]].top(i); dp[cur][j]=q.first+A[i]; if(t>n-m)check(ans,dp[cur][j]); que[cur].push(P(dp[cur][j],t)); } } Pt(ans); putchar('\n'); return 0; }由于优先队列的常数比较大，因此以上代码仍然跑不过 1s ，我们有一种更好的维护最小值的方法。不用优先队列，怎么办呢？我们知道，对于每一个 i ，最终得到的优先队列是固定的，我们只要直接处理出这个队列就行了，就不用push时 pop 了。我们可以用栈来存，只要我们倒着遍历 j ，每次将小于栈顶的元素push进来，因为它肯定比之前的优,那得到的栈就是最终结果了，每次查询时访问栈顶元素即可。
typedef pair<int,int> P; int n,m; struct node{ P num[1005]; int L,R; void push(P x){ if(!R||x.first<num[R-1].first)num[R++]=x; } P top(int x){ if(x-num[R-1].second>m)R--; return num[R-1]; } void clear(){ L=R=0; } node(){L=R=0;} }que[M]; void check(int &a,int b){ if(a==-1||a>b)a=b; } int A[N]; int mod[N]; int dp[M][M]; int main(){ Rd(n);Rd(m); for(int i=1;i<=n;i++)Rd(A[i]); for(int i=1;i<=n;i++)mod[i]=i%m; for(int i=2;i<=m;i++) for(int j=i-1;j>=1;j--){ dp[mod[i]][i-j]=A[i]+A[j]; que[mod[i]].push(P(dp[mod[i]][i-j],j)); } int ans=-1; for(int i=m+1;i<=n;i++){ int cur=mod[i]; que[cur].clear(); for(int j=1;j<m;j++){ int t=i-j; P q=que[mod[t]].top(i); dp[cur][j]=q.first+A[i]; if(t>n-m)check(ans,dp[cur][j]); que[cur].push(P(dp[cur][j],t)); } } Pt(ans); putchar('\n'); return 0; }这样一来，可以学到好多优化 dp 的方式，空间优化可以滚动，时间优化可以用数据结构。
这题切分档很多，每一档都有各自的切法，待我一个一个切过来（毕竟考试的时候很大概率想不到正解，不如学一学怎么切分）。
第一档是最水的，但是考试的时候我没过第4个数据的，实际只要 O(n2) 的，被我活活地加大难度，我当时枚举了起点和终点，然后一路跑，虽然肯定小于 O(n3) ，但也差不多要超了。实际只要从每个点出发 dfs 一遍，求出走过的路径的答案即可。
第二档的因为地图只有15个，所以从每个钥匙处 dfs 一遍就好了。
第三档的特殊性质很好，我们只要在跑的时候 dp 就好了，求出一个节点的最大子链和第二大子链，结果就是两个子链加上自己的权值。
第四档很简单，从1出发 dfs 一遍就好了。
第五档可以用到HDU6070 Dirt Ratio这道题的解法，枚举右端点，然后用线段树维护所有左端点的对应的值，每次向右挪一次右端点时更新一段区间，然后查询最大值即可。
正解的话去看题解了，这太难想了。就是对于一个宝箱，能穿过它的路径的 u 和v，分别有对应的区间，于是在二维坐标图上组成了一个个矩形，坐标图上每个点表示从 u 到v的权值（有几种特殊情况，请看题解）。
#include<vector> #include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #define Max 18 #define M 100005 using namespace std; template <class T> inline void Rd(T &res){ char c;res=0;int k=1; while(c=getchar(),c<48&&c!='-'); if(c=='-'){k=-1;c='0';} do{ res=(res<<3)+(res<<1)+(c^48); }while(c=getchar(),c>=48); res*=k; } template <class T> inline void Pt(T res){ if(res<0){ putchar('\n'); res=-res; } if(res>=10)Pt(res/10); putchar(res%10+48); } struct edge{ int v,nxt; }e[M<<1]; struct node{ int x,y,z; }s[M]; int n,m,edgecnt,tim; int head[M],fa[Max][M],top[M],L[M],R[M],son[M],dep[M],sz[M]; int degree[M]; int LCA(int u,int v){ while(top[u]!=top[v]){ if(dep[top[u]]>dep[top[v]])u=fa[0][top[u]]; else v=fa[0][top[v]]; } return dep[u]<dep[v]?u:v; } vector<int>k[M],t[M]; struct P1{ int ans; bool mark[M]; void dfs(int x,int f,int res){ if(res>ans)ans=res; for(int i=head[x];~i;i=e[i].nxt){ int v=e[i].v; if(v==f)continue; int tmp=0; for(int j=0;j<k[v].size();j++) mark[k[v][j]]=1; for(int j=0;j<t[v].size();j++) if(mark[t[v][j]])tmp+=s[t[v][j]].z; dfs(v,x,res+tmp); for(int j=0;j<k[v].size();j++) mark[k[v][j]]=0; } } void solve(){ for(int i=1;i<=n;i++){ int res=0; for(int j=0;j<k[i].size();j++) mark[k[i][j]]=1; for(int j=0;j<t[i].size();j++) if(mark[t[i][j]])res+=s[t[i][j]].z; dfs(i,-1,res); for(int j=0;j<k[i].size();j++) mark[k[i][j]]=0; } Pt(ans); putchar('\n'); } P1(){ ans=0; memset(mark,0,sizeof(mark)); } }P1; struct P2{ int ans; bool mark[M]; void dfs(int x,int f,int res){ if(res>ans)ans=res; for(int i=head[x];~i;i=e[i].nxt){ int v=e[i].v; if(v==f)continue; int tmp=0; for(int j=0;j<k[v].size();j++) mark[k[v][j]]=1; for(int j=0;j<t[v].size();j++) if(mark[t[v][j]])tmp+=s[t[v][j]].z; dfs(v,x,res+tmp); for(int j=0;j<k[v].size();j++) mark[k[v][j]]=0; } } void solve(){ for(int i=1;i<=m;i++){ int res=0,u=s[i].x; for(int j=0;j<k[u].size();j++) mark[k[u][j]]=1; for(int j=0;j<t[u].size();j++) if(mark[t[u][j]])res+=s[t[u][j]].z; dfs(u,-1,res); for(int j=0;j<k[u].size();j++) mark[k[u][j]]=0; } Pt(ans); putchar('\n'); } P2(){ ans=0; memset(mark,0,sizeof(mark)); } }P2; struct P3{ int ans,fi[M],se[M],val[M]; void dfs(int x,int f){ for(int i=head[x];~i;i=e[i].nxt){ int v=e[i].v; if(v==f)continue; dfs(v,x); if(fi[v]>fi[x]){ se[x]=fi[x]; fi[x]=fi[v]; }else if(fi[v]>se[x])se[x]=fi[v]; } if(ans<fi[x]+se[x]+val[x])ans=fi[x]+se[x]+val[x]; fi[x]=max(0,fi[x]+val[x]); } void solve(){ for(int i=1;i<=n;i++) for(int j=0;j<t[i].size();j++) val[i]+=s[t[i][j]].z; dfs(1,-1); Pt(ans); putchar('\n'); } P3(){ ans=0; memset(fi,0,sizeof(fi)); memset(se,0,sizeof(se)); memset(val,0,sizeof(val)); } }P3; struct P4{ int ans; bool mark[M]; void dfs(int x,int f,int res){ if(res>ans)ans=res; for(int i=head[x];~i;i=e[i].nxt){ int v=e[i].v; if(v==f)continue; int tmp=0; for(int j=0;j<k[v].size();j++) mark[k[v][j]]=1; for(int j=0;j<t[v].size();j++) if(mark[t[v][j]])tmp+=s[t[v][j]].z; dfs(v,x,res+tmp); for(int j=0;j<k[v].size();j++) mark[k[v][j]]=0; } } void solve(){ for(int i=1;i<=1;i++){ int res=0; for(int j=0;j<k[i].size();j++) mark[k[i][j]]=1; for(int j=0;j<t[i].size();j++) if(mark[t[i][j]])res+=s[t[i][j]].z; dfs(i,-1,res); for(int j=0;j<k[i].size();j++) mark[k[i][j]]=0; } Pt(ans); putchar('\n'); } P4(){ ans=0; memset(mark,0,sizeof(mark)); } }P4; struct P5{ struct node{ int L,R,mx,add; }tree[M<<2]; void up(int p){ tree[p].mx=max(tree[p<<1].mx,tree[p<<1|1].mx); } void down(int p){ if(!tree[p].add)return; tree[p<<1].add+=tree[p].add; tree[p<<1].mx+=tree[p].add; tree[p<<1|1].add+=tree[p].add; tree[p<<1|1].mx+=tree[p].add; tree[p].add=0; } void update(int L,int R,int a,int p){ if(tree[p].L==L&&tree[p].R==R){ tree[p].add+=a; tree[p].mx+=a; return; } down(p); int mid=(tree[p].L+tree[p].R)>>1; if(R<=mid)update(L,R,a,p<<1); else if(L>mid)update(L,R,a,p<<1|1); else{update(L,mid,a,p<<1);update(mid+1,R,a,p<<1|1);} up(p); } int query(int L,int R,int p){ if(tree[p].L==L&&tree[p].R==R)return tree[p].mx; down(p); int mid=(tree[p].L+tree[p].R)>>1; if(R<=mid)return query(L,R,p<<1); if(L>mid)return query(L,R,p<<1|1); return max(query(L,mid,p<<1),query(mid+1,R,p<<1|1)); } void build(int L,int R,int p){ tree[p].L=L;tree[p].R=R;tree[p].mx=0;tree[p].add=0; if(L==R)return; int mid=(L+R)>>1; build(L,mid,p<<1); build(mid+1,R,p<<1|1); } int ans,id; int num[M],pos[M]; void dfs(int x,int f){ pos[x]=++id; num[id]=x; for(int i=head[x];~i;i=e[i].nxt) if(e[i].v!=f)dfs(e[i].v,x); } void calc(int st){ id=0; dfs(st,-1); build(1,n,1); for(int i=1;i<=n;i++){ int x=num[i];//当前位置的点 for(int j=0;j<t[x].size();j++){ int y=t[x][j];//第几个宝藏 if(pos[s[y].x]<=i)update(1,pos[s[y].x],s[y].z,1); } ans=max(ans,query(1,i,1)); } } void solve(){ for(int i=1;i<=n;i++) if(degree[i]==1)calc(i); Pt(ans); putchar('\n'); } P5(){ ans=0; } }P5; struct P6{ typedef pair<int,int> p; typedef pair<p,int> P; vector<P>G[M]; int ans,base; int val[M]; struct node{ int L,R,mx,add; }tree[M<<2]; void up(int p){ tree[p].mx=max(tree[p<<1].mx,tree[p<<1|1].mx); } void down(int p){ if(!tree[p].add)return; tree[p<<1].add+=tree[p].add; tree[p<<1].mx+=tree[p].add; tree[p<<1|1].add+=tree[p].add; tree[p<<1|1].mx+=tree[p].add; tree[p].add=0; } void update(int L,int R,int a,int p){ if(tree[p].L==L&&tree[p].R==R){ tree[p].add+=a; tree[p].mx+=a; return; } down(p); int mid=(tree[p].L+tree[p].R)>>1; if(R<=mid)update(L,R,a,p<<1); else if(L>mid)update(L,R,a,p<<1|1); else{update(L,mid,a,p<<1);update(mid+1,R,a,p<<1|1);} up(p); } int query(int L,int R,int p){ if(tree[p].L==L&&tree[p].R==R)return tree[p].mx; down(p); int mid=(tree[p].L+tree[p].R)>>1; if(R<=mid)return query(L,R,p<<1); if(L>mid)return query(L,R,p<<1|1); return max(query(L,mid,p<<1),query(mid+1,R,p<<1|1)); } void build(int L,int R,int p){ tree[p].L=L;tree[p].R=R;tree[p].mx=0;tree[p].add=0; if(L==R)return; int mid=(L+R)>>1; build(L,mid,p<<1); build(mid+1,R,p<<1|1); } void add(int x1,int x2,int y1,int y2,int w){ G[x1].push_back(P(p(y1,y2),w)); G[x2+1].push_back(P(p(y1,y2),-w)); } void rdfs(int x,int f){ if(val[x]){ if(L[x]>1)add(1,L[x]-1,1,L[x]-1,-val[x]); if(L[x]>1&&R[x]<n){ add(1,L[x]-1,R[x]+1,n,-val[x]); add(R[x]+1,n,1,L[x]-1,-val[x]); } if(R[x]<n)add(R[x]+1,n,R[x]+1,n,-val[x]); } for(int i=head[x];~i;i=e[i].nxt){ int v=e[i].v; if(v==f)continue; rdfs(v,x); if(val[x])add(L[v],R[v],L[v],R[v],-val[x]); } } int up(int x,int dis){ for(int k=Max-1;k>=0;k--) if((dis>>k)&1)x=fa[k][x]; return x; } void work(){ build(1,n,1); for(int i=1;i<=n;i++){ for(int j=0;j<G[i].size();j++){ P q=G[i][j]; p qq=q.first; update(qq.first,qq.second,q.second,1); } ans=max(ans,query(1,n,1)+base); } } void solve(){ for(int i=1;i<=m;i++){ int x=s[i].x,y=s[i].y,z=s[i].z; if(x==y)base+=z,val[x]+=z; else{ int lca=LCA(x,y); if(lca==x){ int p=up(y,dep[y]-dep[x]-1); if(L[p]>1)add(1,L[p]-1,L[y],R[y],z); if(R[p]<n)add(R[p]+1,n,L[y],R[y],z); }else if(lca==y){ int p=up(x,dep[x]-dep[y]-1); if(L[p]>1)add(L[x],R[x],1,L[p]-1,z); if(R[p]<n)add(L[x],R[x],R[p]+1,n,z); }else add(L[x],R[x],L[y],R[y],z); } } rdfs(1,-1); work(); Pt(ans); putchar('\n'); } P6(){ ans=0;base=0; memset(val,0,sizeof(val)); } }P6; void add_edge(int u,int v){ e[++edgecnt].v=v;e[edgecnt].nxt=head[u];head[u]=edgecnt; } void dfs(int x,int t){ fa[0][x]=t; L[x]=++tim; sz[x]=1; if(~t)dep[x]=dep[t]+1; for(int i=head[x];~i;i=e[i].nxt){ int v=e[i].v; if(v==t)continue; dfs(v,x); sz[x]+=sz[v]; if(sz[v]>sz[son[x]])son[x]=v; } R[x]=tim; } void rdfs(int x,int t,int tp){ top[x]=tp; for(int i=head[x];~i;i=e[i].nxt){ int v=e[i].v; if(v==t)continue; if(v==son[x])rdfs(v,x,tp); else rdfs(v,x,v); } } bool chk1(){ for(int i=1;i<=m;i++) if(s[i].x!=s[i].y)return false; return true; } bool chk2(){ for(int i=1;i<=m;i++) if(s[i].x!=1)return false; return true; } bool chk3(){ int cnt=0; for(int i=1;i<=n;i++) if(degree[i]==1)cnt++; return cnt==2; } int main(){ int a,b; memset(head,-1,sizeof(head)); memset(fa,-1,sizeof(fa)); Rd(n);Rd(m); for(int i=1;i<n;i++){ Rd(a);Rd(b); add_edge(a,b); add_edge(b,a); degree[a]++; degree[b]++; } dfs(1,-1); rdfs(1,-1,1); for(int k=0;k<Max;k++) for(int i=1;i<=n;i++) if(~fa[k][i])fa[k+1][i]=fa[k][fa[k][i]]; for(int i=1;i<=m;i++){ Rd(s[i].x);Rd(s[i].y);Rd(s[i].z); k[s[i].x].push_back(i); t[s[i].y].push_back(i); } if(n<=1000&&m<=1000)P1.solve(); else if(m<=15)P2.solve(); else if(chk1())P3.solve(); else if(chk2())P4.solve(); else if(chk3())P5.solve(); else P6.solve(); return 0; }T1巧妙运用递归，T2 dp 时间和空间优化，T3各种切分，写得的确很爽。
