【BZOJ】 4813: [Cqoi2017]小Q的棋盘-白红宇

【BZOJ】 4813: [Cqoi2017]小Q的棋盘

阅读量：5174 次

发布时间：2019-06-13

本文共 1088 字，大约阅读时间需要 3 分钟。

题目链接：

暴力转移就好，考虑以某一个点为根的子树分为是否走回来两种情况

${f_{i,j}}$表示已点$i$为根的子树，走了$j$步之后回到点$i$最多能经过多少个点

${g_{i,j}}$表示已点$i$为根的子树，走了$j$步之后不管停在那个点最多能经过多少个点

写了个${n^{2}}$转移

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             10 using namespace std;11 #define llg int12 #define maxn 21013 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);14 vector
              
               a[maxn];15 llg f[maxn][maxn],g[maxn][maxn],n,m;16 inline llg getint()17 {18 llg w=0,q=0; char c=getchar();19 while((c<'0' || c>'9') && c!='-') c=getchar();20 if (c=='-') q=1, c=getchar(); while (c>='0' && c<='9') w=w*10+c-'0', c=getchar();21 return q ? -w : w;22 }23 24 void init()25 {26 cin>>n>>m;27 for (llg i=1;i
               
                =1;i--)44 {45 for (llg j=0;j
                
                 =2)48 {49 f[x][i]=max(f[x][i],f[v][j]+f[x][i-j-2]);50 g[x][i]=max(g[x][i],f[v][j]+g[x][i-j-2]);51 }52 g[x][i]=max(g[x][i],g[v][j]+f[x][i-j-1]);53 }54 }55 }56 for (llg i=0;i