这个题目算是一个思维题，主要要想明白。
如果不都是输出-1的话，肯定有一步就可以到的，所以就先把一步可以到的找出来，
然后再找两步可以到达的，有点像bfs，所以就用队列写吧。
这个主要就是要想清楚，知道所以的n步都是由n-1步得到的就可以了。
#include <bits/stdc++.h> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; const int maxn=2e5+5; typedef long long ll; int a[maxn],ans[maxn]; vector<int>G[maxn]; queue<int>que; int main(){ int n; scanf("%d",&n); memset(ans,inf,sizeof(ans)); while(!que.empty()) que.pop(); for(int i=1;i<=n;i++) scanf("%d",&a[i]),G[i].clear(); for(int i=1;i<=n;i++){ if(i+a[i]<=n&&(a[i]&1)^(a[i+a[i]]&1)){ que.push(i); ans[i]=1; } else if(i-a[i]>=1&&(a[i]&1)^(a[i-a[i]]&1)){ que.push(i); ans[i]=1; } if(i+a[i]<=n) G[i+a[i]].push_back(i); if(i-a[i]>=1) G[i-a[i]].push_back(i); } while(!que.empty()){ int u=que.front();que.pop(); for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(ans[v]>ans[u]+1) ans[v]=ans[u]+1,que.push(v); } } for(int i=1;i<=n;i++){ if(ans[i]>=inf) printf("-1 "); else printf("%d ",ans[i]); } return 0; }
这个是一个三维的dp，
dp[i][j][k]表示满足 s 串的前面 i 个， t 串的前面 j 个，答案串的前缀和为 k 的最小长度
知道定义了转移就很好写了。
然后用背包的方式记录路径。
写的略带复杂。
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <stack> #define fir first #define sec second #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; const int maxn=1e5+10; int dp[220][220][420]; char str[220][220][220]; char s[220],t[220]; vector<char>ex; struct node{ int x,y,z; node(int x=0,int y=0,int z=0):x(x),y(y),z(z){} }path[220][220][420];; int main(){ scanf("%s%s",s+1,t+1); int slen=strlen(s+1),tlen=strlen(t+1); memset(dp,inf,sizeof(dp)); dp[0][0][0]=0; for(int i=0;i<=slen;i++){ for(int j=0;j<=tlen;j++){ for(int k=0;k<=slen+tlen;k++){ int res=dp[i][j][k]; if(s[i]==t[j]){ if(s[i]=='('&&k>0){ if(dp[i-1][j-1][k-1]<res){ res=dp[i-1][j-1][k-1]; path[i][j][k]=node(i-1,j-1,k-1); str[i][j][k]='('; } } if(s[i]==')') { if(dp[i-1][j-1][k+1]<res){ res=dp[i-1][j-1][k+1]; path[i][j][k]=node(i-1,j-1,k+1); str[i][j][k]=')'; } } } else{ if(s[i]=='('&&k>0) { if(dp[i-1][j][k-1]<res){ res=dp[i-1][j][k-1]; path[i][j][k]=node(i-1,j,k-1); str[i][j][k]='('; } } if(t[j]=='('&&k>0) { if(dp[i][j-1][k-1]<res){ res=dp[i][j-1][k-1]; path[i][j][k]=node(i,j-1,k-1); str[i][j][k]='('; } } if(s[i]==')') { // printf("sss %d ",dp[i-1][j][k+1]); if(dp[i-1][j][k+1]<res){ res=dp[i-1][j][k+1]; path[i][j][k]=node(i-1,j,k+1); str[i][j][k]=')'; } } if(t[j]==')') { if(dp[i][j-1][k+1]<res){ res=dp[i][j-1][k+1]; path[i][j][k]=node(i,j-1,k+1); str[i][j][k]=')'; } } } if(k>0) { if(dp[i][j][k-1]<res){ res=dp[i][j][k-1]; path[i][j][k]=node(i,j,k-1); str[i][j][k]='('; } } dp[i][j][k]=min(dp[i][j][k],res+1); // printf("dp[%d][%d][%d]=%d %c ",i,j,k,dp[i][j][k],str[i][j][j]); } } } int ans=inf,mark=0; for(int k=0;k<=slen+tlen;k++){ if(dp[slen][tlen][k]+k<ans){ ans=dp[slen][tlen][k]+k; mark=k; // printf("dp[%d][%d][%d]=%d ",slen,tlen,k,dp[slen][tlen][k]); } } int a=slen,b=tlen,c=mark; while(mark){ ex.push_back(')'); mark--; } while(1){ // printf("str[%d][%d][%d]=%c ",a,b,c,str[a][b][c]); ex.push_back(str[a][b][c]); node u=path[a][b][c]; a=u.x,b=u.y,c=u.z; if(a==0&&b==0&&c==0) break; } // printf("%d ",ans); int len=ex.size(); for(int i=len-1;i>=0;i--) printf("%c",ex[i]); printf(" "); return 0; }