[关闭]
@Junlier 2018-08-31T22:12:49.000000Z 字数 1356 阅读 1963

小Q的棋盘 (贪心)

贪心

题目

洛谷传送门

做法

  1. 显然这是一棵树(这个就不多bb了,树的性质)
  2. 很容易发现一个性质,如果一条链走完,我们必须回头再走一次那条链(或一部分)才可以走到更多的点
  3. 所以为了减少这个损失,我们以最长链(从起点开始的最长链)的终点(最低端)为终点(步数走完不须回头),既然做到减少了最多的不必要,那么这样一定会是最优的。(可以证明是最优的,只是我不知道,举不出反例我就写了)
  4. 考虑除了走最长链步数之外的剩余步数。最好画个图,既然我们一定要走最长链,那么可以看做一根树干上长了其他的一些枝条,我们的剩余步数就是用来走这些地方的,很容易证明一定可以额外走到 (剩余步数/2) 个节点(最长链之外)。
  5. 没了……(代码实现基本没难度)

code(没有注释=_=)

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<iomanip>
  7. #include<algorithm>
  8. #include<ctime>
  9. #include<queue>
  10. #include<stack>
  11. #include<vector>
  12. #define rg register
  13. #define il inline
  14. #define lst long long
  15. #define ldb long double
  16. #define N 150
  17. using namespace std;
  18. const int Inf=1e9;
  19. int n,step,cnt;
  20. int ans,ans_st;
  21. struct EDGE{
  22. int to,nxt;
  23. }ljl[N<<1];
  24. int hd[N];
  25. int vis[N];
  26. il int read()
  27. {
  28. rg int s=0,m=0;rg char ch=getchar();
  29. while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  30. while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  31. return m?-s:s;
  32. }
  33. il void add(rg int p,rg int q)
  34. {
  35. ljl[++cnt]=(EDGE){q,hd[p]},hd[p]=cnt;
  36. }
  37. void dfs(rg int fm,rg int now,rg int st,rg int ss)
  38. {
  39. if(st>step)return;
  40. if(ss>ans)ans=ss,ans_st=st;
  41. vis[now]=1;
  42. for(rg int i=hd[now];i;i=ljl[i].nxt)
  43. {
  44. rg int qw=ljl[i].to;
  45. if(qw==fm)continue;
  46. if(!vis[qw])dfs(now,qw,st+1,ss+1);
  47. }
  48. }
  49. int main()
  50. {
  51. n=read(),step=read();
  52. for(rg int i=1;i<n;++i)
  53. {
  54. rg int p=read(),q=read();
  55. add(p,q),add(q,p);
  56. }
  57. dfs(0,0,0,1);
  58. if(ans_st==step)printf("%d\n",ans);
  59. else printf("%d\n",min(ans+(step-ans_st)/2,n));
  60. return 0;
  61. }

代码还是很好看的,只是变量为了通俗就很丑

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注