F
给你ABC三个串 让你求D串
D是AB的子序列 C是D的子串
求D的长度
求出C在AB中出现的位子记录开始位子和结束位子
n^2 枚举在A中位子和在B中位子
然后得到AB 开始位子之前的lcs 和AB结束位子的lcs
开始预处理一下lcs
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #include <cstring> #include <string> #include<set> #include<deque> #include<queue> #include<stack> using namespace std; #define inf 1000000007 #define MAXN 1010 #define ll long long char a[MAXN],b[MAXN],c[MAXN]; int dp1[MAXN][MAXN],dp2[MAXN][MAXN]; struct node { int ind1,ind2; }x1[MAXN],x2[MAXN]; int main() { int t; scanf("%d",&t); int ca=1; while(t--) { scanf("%s%s%s",a+1,b+1,c+1); int len=strlen(c+1); int len1=strlen(a+1); int len2=strlen(b+1); memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { if(a[i]==b[j]) dp1[i][j]=dp1[i-1][j-1]+1; else dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1]); } } for(int i=len1;i>=1;i--) { for(int j=len2;j>=1;j--) { if(a[i]==b[j]) dp2[i][j]=dp2[i+1][j+1]+1; else dp2[i][j]=max(dp2[i+1][j],dp2[i][j+1]); } } int cnt1,cnt2; cnt1=cnt2=0; for(int i=1;i<=len1;i++) { if(a[i]==c[1]) { int k=2; int j; for(j=i+1;j<=len1&&k<=len;j++) { if(c[k]==a[j]) { k++; } } if(k==len+1) { x1[cnt1].ind1=i-1; x1[cnt1].ind2=j; cnt1++; } } } for(int i=1;i<=len2;i++) { if(b[i]==c[1]) { int k=2; int j; for(j=i+1;j<=len2&&k<=len;j++) { if(c[k]==b[j]) { k++; } } if(k==len+1) { x2[cnt2].ind1=i-1; x2[cnt2].ind2=j; cnt2++; } } } int mx=0; for(int i=0;i<cnt1;i++) { for(int j=0;j<cnt2;j++) { mx=max(mx,dp1[x1[i].ind1][x2[j].ind1]+dp2[x1[i].ind2][x2[j].ind2]+len); } } printf("Case #%d: %d ",ca++,mx); } return 0; }
D
n个点n-1条边 你只可以去掉一条 花费是 这条边的权 * （块里面最大的距离） 要求这个最小
显然这个和树的直径有关 那么先2遍dfs求树的直径
然后枚举每条边 1 这条边在直径上 那么要求的就是边两端点对应的子树的最大深度
2 不在直径上 那么就是边权*直径
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define inf 2e9+7 #define MAXN 100010 int head[MAXN]; struct node { int v,w,next,id; }edge[MAXN<<1]; int ds[MAXN],dt[MAXN],cnt,ms[MAXN],mt[MAXN]; void add(int u,int v,int w,int id) { edge[cnt].id=id; edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } void dfs(int u,int fa) { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v==fa) continue; ds[v]=ds[u]+1; dfs(v,u); } } void dfs1(int u,int fa) { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v==fa) continue; dt[v]=dt[u]+1; dfs1(v,u); } } void dfs2(int u,int fa) { mt[u]=dt[u]; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v==fa) continue; dfs2(v,u); mt[u]=max(mt[u],mt[v]); } } void dfs3(int u,int fa) { ms[u]=ds[u]; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v==fa) continue; dfs3(v,u); ms[u]=max(ms[u],ms[v]); } } int id,ans,len; void dfs4(int u,int fa) { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v==fa) continue; if(ds[u]+dt[v]+1==len) { if(max(ms[u],mt[v])*edge[i].w<ans) { ans=max(ms[u],mt[v])*edge[i].w; id=edge[i].id; } else if(max(ms[u],mt[v])*edge[i].w==ans&&edge[i].id<id) id=edge[i].id; } else { if(len*edge[i].w<ans) { ans=len*edge[i].w; id=edge[i].id; } else if(len*edge[i].w==ans&&edge[i].id<id) id=edge[i].id; } dfs4(v,u); } } int main() { int t; scanf("%d",&t); int ca=1; while(t--) { int n; scanf("%d",&n); cnt=0; memset(head,-1,sizeof(head)); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w,i); add(v,u,w,i); } ds[1]=0; dfs(1,-1); int s=1; for(int i=1;i<=n;i++) if(ds[i]>ds[s]) s=i; ds[s]=0; dfs(s,-1); int tt=1; len=ds[1]; for(int i=1;i<=n;i++) if(ds[i]>ds[tt]) { tt=i; len=ds[i]; } dt[tt]=0; dfs1(tt,-1); dfs2(s,-1); dfs3(tt,-1); ans=inf; dfs4(s,-1); printf("Case #%d: %d ",ca++,id); } return 0; }