<blockquote id="shwb3"><ruby id="shwb3"></ruby></blockquote>
  • <small id="shwb3"><strong id="shwb3"></strong></small>

      1. <big id="shwb3"></big>
        1. 首页 > 其他 > 详细

          依赖性背包

          时间:2019-03-26 22:23:47      阅读:34      评论:0      收藏:0      [点我收藏+]

          标签:处理   地方   col   i++   方程   char   开始   isdigit   back   

          技术分享?#35745;? src=

          某位大佬的题解:

          给树形DPの初学者(其实就是我哈哈(?•??•?)??)

          其实这个题不知道为什么是提高+/省选-

          还是比较简单的

          瞄一眼下去就是DP

          但是怎么DP呢?

          可以发现学习课程是有顺序的

          我马上想到了DAG

          然后又发现每门课有最多有一个先修课

          所以这一定是一个森林

          为了方便处理也是为了迎合输入数据

          就把0号节点看做根节点即可

          这样实质上就什么也不?#20040;?#29702;

          只需要在考虑的时候

          把0号节点列入必选的范围即可

          即要选m+1门课

          (我看楼下这些问题都有讲,但是唯独状态转移方程是怎么推出来的没有讲,可能是觉得太简单了吧.但是DP最核心的部分就是推状态转移方程啊,而且这恰恰是新手最欠缺的地方,我觉得来看题解的人都是来看这个的吧(划掉))

          解决了这个问题之后

          我们就考虑怎么在树上DP就行了

          DP的核心是状态的设计和重叠的?#28216;?#39064;结构

          我们发现

          树本身就是一个递归的结构

          所以考虑在每棵子树上DP

          然后合并就行了

          怎么在子树上DP呐(???з??)?

          因为DP的一个核心思想是从最简单的?#28216;?#39064;开始,逐步扩大?#28216;?#39064;规模

          所以我们?#27604;?#35201;从最简单的状态讲起

          一棵子树最简单的状态是啥?

          对一棵子树,要想选其中的点,根节点是必须选的

          所以不妨设根节点为1号节点

          然后按我们存图的顺序依次给每个儿子编号(从2(到儿子的个数+1))

          这样状态就好设计了

          不妨设f[now][j][k]表示以now为根节点的子树

          考虑前j个节点选k门课的方案数

          因为1号节点是根节点,显然递推起点f[now][1][1]=val[now]

          这样很容易得到状态转移方程

          f[now][j][k]=max(f[now][j-1][k],f[son][所有节点数][l]+f[now][j-1][k-l]);

          然后我们观察等式两边的特点

          哪些是我?#19988;?#30693;的?

          在对now求解前

          我们至少已经处理完了前面的子树

          所以f[son][所有节点数][l]

          是可以直接用的

          然后 在处理第j个节点前

          前j-1个节点是我?#19988;?#32463;处理过的

          所以f[now][j-1][k]和f[now][j-1][k-l]也不?#27599;?#34385;循环顺序问题

          但是问题来了

          这样开三维数组不会炸空间吗

          也许本题不会

          但是我们可以很显然的发现

          空间是可以优化的

          只要稍稍改变循环顺序即可

          我要用到j-1的内容

          都是满足l<k的

          所以倒着循环k

          这样就可以使我们在一个数组中当前值和上面我们用到的值完全不影响

          就酱~

          最后的状态转移方程在代码里

          个人实现的代码:

          #include<bits/stdc++.h>
          using namespace std;
          const int maxn=310;
          vector<int> son[maxn];
          int f[maxn][maxn],r[maxn],n,m; //f[i][j]表示在节点i的子树上选了j个课程. 
          inline int read()
          {
              int x=0,ff=1;
              char ch=getchar();
              while(!isdigit(ch))
              {
                  if(ch==-) ff=-1;
                  ch=getchar();
              }
              while(isdigit(ch))
              {
                  x=(x<<1)+(x<<3)+(ch^48);
                  ch=getchar();
              }
              return x*ff;
          }
          inline void put(int x)
          {
              if(x<0) putchar(-),x=-x;
              if(x>9) put(x/10);
              putchar(x%10+0);
          }
          inline void dp(int x)
          {
              f[x][1]=r[x];              //初始状态即必须选x。 
              for(int i=0;i<son[x].size();i++)
              {
                  int y=son[x][i];
                  dp(y);
                  for(int t=m+1;t>=1;t--) //以x为节点的选的课程,1为必须给x留一个空间.逆序符合背包. 
                  {
                      for(int k=0;k<=t-1;k++)  //x的儿?#28216;?#33410;点选的课程,同样t-1也是保证必须给x留一个空间. 
                      {
                          f[x][t]=max(f[x][t],f[x][t-k]+f[y][k]);
                      }
                  }
              }
          }
          int main()
          {
              //freopen("1.in","r",stdin);
              n=read();m=read();
              for(int i=1;i<=n;i++)
              {
                  int x=read(),y=read();
                  if(x) son[x].push_back(i);
                  else   son[0].push_back(i);
                  r[i]=y;
              }
              dp(0);
              put(f[0][m+1]);
              return 0;
          }

           

          依赖性背包

          标签:处理   地方   col   i++   方程   char   开始   isdigit   back   

          原文:https://www.cnblogs.com/gcfer/p/10604114.html

          (0)
          (0)
             
          举报
          评论 一句话评论(0
          0条  
          登录后才能评论!
          ? 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
          打开技术之扣,分享程序人生!
                       

          鲁公网安备 37021202000002号

          t6娱乐平台官方
          <blockquote id="shwb3"><ruby id="shwb3"></ruby></blockquote>
        2. <small id="shwb3"><strong id="shwb3"></strong></small>

            1. <big id="shwb3"></big>
              1. <blockquote id="shwb3"><ruby id="shwb3"></ruby></blockquote>
              2. <small id="shwb3"><strong id="shwb3"></strong></small>

                  1. <big id="shwb3"></big>