怎么自己做网站推广,入门级网页设计培训学员,几何背景生成网站,大连旅顺problem
luogu-P3698
solution1-贪心
显然我们想尽可能地少走回头路#xff0c;即一直往下走。
所以我们可以都会有个初步地猜测是走最长链。
但很快就会想到万一这是一条单链#xff0c;链中的点都是二度点#xff0c;走得越深回头浪费的步数也越多。
然后就可能直接…problem
luogu-P3698
solution1-贪心
显然我们想尽可能地少走回头路即一直往下走。
所以我们可以都会有个初步地猜测是走最长链。
但很快就会想到万一这是一条单链链中的点都是二度点走得越深回头浪费的步数也越多。
然后就可能直接把这种想法抛却了。
以上都是脑中不到两分钟的粗略思路很容易误判。
实际上仔细想想建议画几个树就会发现最优解总可以调整成走长链。
当开始走长链的时候就一定不会走回头路了。
考虑一条链当走到底的时候发现有多余的步数然后又发现链中某点有多个儿子我们现在才返回去走一条新链的话这个浪费的步数就太多了。
所以我们应当是预知有多余的步数然后再走到那个点的时候就先走新链然后再倒回来继续走这条链。
对于新链而言一样按照上面的预知流程执行。
可以感觉地到这是个递归的过程。
但这并不是代码实现这只是来佐证贪心猜测的正确性的。
这也是网上题解说的 走完最长链上的点后每两步能到达一个新的点 这不是代表着一定是先走完最长链再回头还是最优解可以将步数和点数按照这种方式对应上。
时间复杂度 O(n)O(n)O(n)所以说出题人完全可以将 nnn 开大点卡掉 dpdpdp 的做法。
为你的良心点赞
code1
#include bits/stdc.h
using namespace std;
#define maxn 105
vector int G[maxn];
int n, m, ans;void dfs( int u, int fa, int dep ) {ans max( ans, dep );for( int v : G[u] ) if( v fa ) continue;else dfs( v, u, dep 1 );
}int main() {scanf( %d %d, n, m );for( int i 1, u, v;i n;i ) {scanf( %d %d, u, v );G[u].push_back( v );G[v].push_back( u );}dfs( 0, 0, 1 );if( m ans ) printf( %d\n, m 1 );else printf( %d\n, min( n, ans (m - ans 1) / 2 ) );return 0;
}solution2-树形dp
这种样子长得就像个树形 dpdpdp。
设 f(i,j):f(i,j):f(i,j): 在以 iii 为根的子树内从 iii 开始向下在子树内走了 jjj 步最多经过的节点数。
然后可能就直接从上往下用 fafafa 的 fff 更新 uuu 的 fff 此时有新加点
然后搜索 uuu 子树完了回来又从下往上更新此时不会有新加点。
实际上这种做法的正确性必须保证对于一棵树 dfs\text{dfs}dfs 先搜的就是最长链相当于是跑的贪心。
实在不理解的可以自己写个数据生成器不用多大 888 以内都能给你排出错误来。
其实问题与贪心思考的一样就是是否回到这个点来。我们将这个变成第三维。
设 f(i,j,0/1):0f(i,j,0/1):0f(i,j,0/1):0 不回到 uuu 点111 回到 uuu 点。
则对于 uuu 枚举儿子 vvv以及自己一共在子树内走的步数和 vvv 在子树内走的步数 {f(u,i,0)max{f(u,i−j,1)f(v,j−1,0),f(u,i−j,0)f(v,j−2,1)}f(u,i,1)max{f(u,i−j,1)f(v,j−2,1)}\begin{cases} f(u,i,0)\max\Big\{f(u,i-j,1) f(v,j-1,0),f(u,i-j,0) f(v,j-2,1)\Big\}\\ f(u,i,1)\max\Big\{f(u,i-j,1) f(v,j-2,1)\Big\} \end{cases} ⎩⎨⎧f(u,i,0)max{f(u,i−j,1)f(v,j−1,0),f(u,i−j,0)f(v,j−2,1)}f(u,i,1)max{f(u,i−j,1)f(v,j−2,1)} 回来的话 u−vu-vu−v 这条边就要走两次所以是 −2-2−2否则 −1-1−1。
时间复杂度 O(n3)O(n^3)O(n3)。
哪哪儿都比不上贪心好吧
code2
#include bits/stdc.h
using namespace std;
#define maxn 105
vector int G[maxn];
int n, m;
int f[maxn][maxn][2];void dfs( int u, int fa ) {f[u][0][1] f[u][0][0] 1;for( int v : G[u] )if( v ^ fa ) {dfs( v, u );for( int i m;i;i -- )for( int j 1;j i;j ) {if( j 0 ) f[u][i][0] max( f[u][i][0], f[u][i - j][1] f[v][j - 1][0] );if( j 1 ) f[u][i][0] max( f[u][i][0], f[u][i - j][0] f[v][j - 2][1] );if( j 1 ) f[u][i][1] max( f[u][i][1], f[u][i - j][1] f[v][j - 2][1] );}}
}int main() {scanf( %d %d, n, m );for( int i 1, u, v;i n;i ) {scanf( %d %d, u, v );G[u].push_back( v );G[v].push_back( u );}dfs( 0, 0 );int ans 0;for( int i 0;i m;i ) ans max( ans, max( f[0][i][1], f[0][i][0] ) );printf( %d\n, ans );return 0;
}
