注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj1017  

2013-01-23 18:14:01|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

魔兽地图是道裸的树形dp,但是对我而言很难。

我看了各种题解,大概有了些自己的理解吧

F[i][j][k]表示i物品贡献给父亲j个花了k的最大力量

首先F[i][j][k]=max{F[i][j'][k]+(j'-j)*power[i]}

然 后对于儿子,有F[i][j][k]=max{F[i][j][k],F[son][T[son]*j][p]+F[i][j][k-p]}首先要讲的是 这里用了徐持衡在论文里提到的nc复杂度树形背包的思想,在转移过程中的F[i][j][k]仅仅充当各个儿子的函数值的合并操作的工具而已。

然后我一开始最纠结的就是为什么一定是F[son][T[son]*j][p]呢?不可以儿子贡献一个>T[son]*j的数目然后自己在私吞一部分用来造自己吗?

经过良久思索,终于恍然大悟:如果是这样的话,在第一个方程式中会被算进去。

最后就是无意义的状态不能参加转移

这道题过的最累

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define MAXN 60
#define MAXP 110
#define MAXM 2010
using namespace std;
int F[MAXN][MAXP][MAXM],G[MAXM],ans;
int n,m,power[MAXN],cost[MAXN],can[MAXN],father[MAXN];
int tot,num[MAXN],next[MAXN],need[MAXN],start[MAXN];
void make(int a,int b,int c){  tot++,num[tot]=b,need[tot]=c,next[tot]=start[a],start[a]=tot;  }
void dfs(int p)
{
    if(start[p]==0)
    {
        can[p]=min(can[p],m/cost[p]);
        for(int i=0;i<=can[p];i++)
            for(int j=i;j<=can[p];j++)
                F[p][i][j*cost[p]]=(j-i)*power[p];
        return ;
    }
    can[p]=1<<30;
    for(int i=start[p];i;i=next[i])
        dfs(num[i]),can[p]=min(can[p],can[num[i]]/need[i]);
    for(int i=0;i<=can[p];i++)
        F[p][i][0]=0;
    for(int i=start[p],v=num[i];i;i=next[i],v=num[i])
        for(int j=0;j<=can[p];j++)
        {
            memcpy(G,F[p][j],sizeof(F[p][j]));
            memset(F[p][j],-1,sizeof(F[p][j]));
            for(int k=m;k>=0;k--)
            {
                for(int r=k;r>=0;r--)
                    if(G[k-r]!=-1&&F[v][j*need[i]][r]!=-1)
                        F[p][j][k]=max(F[p][j][k],G[k-r]+F[v][j*need[i]][r]);
                ans=max(ans,F[p][j][k]);
            }
        }
    for(int i=0;i<=can[p];i++)
        for(int j=i;j<=can[p];j++)
            for(int k=0;k<=m;k++)
                if(F[p][j][k]!=-1)
                    F[p][i][k]=max(F[p][i][k],F[p][j][k]+(j-i)*power[p]),ans=max(ans,F[p][i][k]);
}
void read()
{
    char type;
    scanf("%d %d",&n,&m);
    for(int i=1,p,a,b;i<=n;i++)
    {
        scanf("%d %c",&power[i],&type);
        if(type=='B'scanf("%d %d",&cost[i],&can[i]);
        else
            for(scanf("%d",&p);p>=1;p--)
            {
                scanf("%d %d",&a,&b);
                make(i,a,b),father[a]=i;
            }
    }
    memset(F,-1,sizeof(F));
    for(int i=1;i<=n;i++)
        if(father[i]==0)
            dfs(i);
}
int main()
{
    read();
    printf("%d\n",ans);
    return 0;
}
  评论这张
 
阅读(909)| 评论(3)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017