V
主页
【算法进阶】【动态规划百练】会这一题，区间dp就掌握了！CF1771D Hossam and (sub-)palindromic tree - 信息学奥赛
发布人
在面向代码编程之前，先关注一个呗 #include<bits/stdc++.h> using namespace std;const int N=2e3+2;vector<int> v[N]; int T,n,dp[N][N],x,y,h,f[N][N],i,j,ans;char a[N],c; inline int read(){ h=0,c=getchar(); while(!(c>='0'&&c<='9'))c=getchar(); while(c>='0'&&c<='9')h=(h<<1)+(h<<3)+(c^48),c=getchar(); return h; } inline void dfs(int rt,int x,int fa){ f[rt][x]=fa; for(int t:v[x])if(t!=fa)dfs(rt,t,x); } inline int d(int x,int y){ if(x==0||y==0)return -1e9; if(dp[x][y]!=-1)return dp[x][y]; if(x==y)return 1; if(f[y][x]==y)return (a[x]==a[y])+1; return dp[x][y]=max(max(d(f[y][x],f[x][y])+2*(a[x]==a[y]), d(f[y][x],y)),d(x,f[x][y])); } int main(){ scanf("%d",&T); while(T--){ scanf("%d%s",&n,a+1),ans=0; for(i=1;i<=n;i++) v[i].clear(),fill(dp[i]+1,dp[i]+n+1,-1); for(i=1;i<n;i++)x=read(),y=read(), v[x].push_back(y),v[y].push_back(x); for(i=1;i<=n;i++)dfs(i,i,0); for(i=1;i<=n;i++)for(j=1;j<=n;j++)ans=max(ans,d(i,j)); printf("%d\n",ans); } return 0; }
打开封面
下载高清视频
观看高清视频
视频下载器
【算法进阶】【动态规划-4区间与环形动态规划】区间与环形动态规划，破环成链，P1775 石子合并（弱化版） P4170 涂色 P1880 石子合并 -信息学奥赛
【算法进阶】【动态规划-7数位动态规划】最简单的dp-数位dp！数位dp知识点与例题Segment Sum详解-信息学竞赛
【算法进阶】【字符串-AC自动机】AC自动机算法原理及实现精讲+代码 - 信息学奥赛
【算法进阶】【动态规划-5树形动态规划】树形dp例题精讲、杂题泛讲-信息学竞赛
【算法进阶】【杂题选讲】Minimum spanning tree for each edge最小生成树&树上倍增练习题-信息学竞赛
【算法进阶】【动态规划百练-IOI1998 Polygon】上古IOI动态规划题目讲解-信息学竞赛
【算法进阶】【动态规划百练】矩阵快速幂优化动态规划P2151[SDOI2009]HH去散步-信息学竞赛
【算法进阶】【基环树基础】基环树dp P2607[ZJOI2008]骑士 基环树+tarjan边双连通分量+树形动态规划+线性动态规划-信息学竞赛
【算法进阶】【树分块】树分块，得分利器！bitset维护答案 P6177 Count on a tree II/【模板】树分块-信息学竞赛
【算法进阶】【动态规划百练】简单数位dp题目P2188 小Z的 k 紧凑数-信息学竞赛
【算法进阶】【动态规划百练】单调队列优化动态规划P3572[POI2014]PTA-Little Bird-信息学竞赛
【算法进阶】【动态规划百练】思维与线段树优化动态规划[ARC159D] LIS 2-信息学竞赛
【算法进阶】【动态规划百练】思维+状态压缩动态规划CF1391D 505-信息学竞赛
【算法进阶】【字符串-KMP算法】字符串匹配经典算法，图例讲解，AC自动机的基础！P3375 【模板】KMP字符串匹配 - 信息学奥赛
【算法进阶】【贪心-过河问题】更复杂的贪心，过河问题情况详解-信息学竞赛
【算法进阶】【数据结构百练】ST表 单调队列 线段树 CF1195E OpenStreetMap-信息学竞赛
【算法进阶】【动态规划百练】状压dp货郎挑担问题CF8C Looking for Order-信息学竞赛
【算法进阶】【点分治】图解点分治模板及例题讲解-信息学竞赛
【算法进阶】【动态RMQ/杂题选讲】动态RMQ/P1198 [JSOI2008] 最大数 精讲+代码 - 信息学奥赛
【算法进阶】【线段树的应用】线段树维护动态区间最大子段和P4513 小白逛公园-信息学竞赛
【算法进阶】【动态规划百练】简单状压dp与滚动数组优化 P5005 中国象棋 - 摆上马 -信息学竞赛
近期，信息学奥赛培训机构向家长收高额学费
【算法进阶】【反悔贪心】反悔贪心及例题CF865D Buy Low Sell High讲解-信息学竞赛
【算法强化】【综合性杂题选讲-2】Kruskal重构树+可持久化线段树 P7834[ONTAK2010]Peaks加强版-信息学竞赛
【算法进阶】【杂题选讲】【P2034 选择数字】从普通dp入手，带你一步步走向正解，感受做题思考的过程
【算法进阶】【严格次小生成树】Kruskal最小生成树+树上倍增详解-信息学竞赛
【算法进阶】【动态规划-8概率与期望动态规划】dp，永远的噩梦？并不是！代码最短的dp题！CF235B Let's Play Osu!-信息学竞赛
【算法进阶】【树链剖分】树链剖分（重链剖分）精讲-信息学竞赛
【算法进阶】【简单交互题】交互题简介与简单例题讲解-信息学竞赛
【算法进阶】【动态规划百练】状态压缩动态规划+BFS P2622 关灯问题II-信息学竞赛
【算法进阶】【数论分块（整除分块）】数论分块与经典例题讲解-信息学竞赛
【算法进阶】【数论-组合初步】排列组合二项式定理Lucas定理P1350车的放置精讲-信息学竞赛
认真学习，认证干饭
【赛题讲解】【AtCoder Beginner Contest 305】G-Banned Substrings AC自动机+矩阵快速幂优化动态规划-信息学竞赛
【算法进阶】【字符串-马拉车manacher】manacher求回文子串，例题[国家集训队] 最长双回文串讲解-信息学竞赛
【算法进阶】【带权并查集/并查集复习】最后一次学习简单并查集！学不会以后各种算法都听不懂！ - 信息学竞赛
【算法进阶】【可持久化线段树的应用】可持久化线段树的构建与应用，静态区间mex问题-信息学竞赛
【算法进阶】【网络流建模】dinic算法的应用，网络流建模例题-信息学竞赛
【算法进阶】【数据结构-树状数组】树状数组及二维树状数组讲解-信息学竞赛
【算法强化】【斜率优化动态规划】动态规划的优化之斜率优化DP-信息学竞赛
