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

Xorex's blog

纵然希望渺茫,也要做一条有梦想的咸鱼!

 
 
 
 
 

日志

 
 
关于我

本人倒是一直被吊着打啊……

文章分类

树形DP(2)  

2017-05-01 11:53:59|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
下面看下一道题
P1305 选课
学校实行学分制。每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分。学校开设了N(N<300)门的选修课程,每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。
   在选修课程中,有些课程可以直接选修,有些课程需要一定的基础知识,必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号,依次为1,2,3,…。
你的任务是为自己确定一个选课方案,使得你能得到的学分最多,并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。
然后输出选择的课程,按照编号从小到大输出。
输入:
输入文件的第一行包括两个整数N、M(中间用一个空格隔开),其中1≤N≤300,1≤M≤N。 以下N行每行代表一门课。课号依次为1,2,…,N。每行有两个数(用一个空格隔开),第一个数为这门课先修课的课号(若不存在先修课则该项为0),第二个数为这门课的学分。学分是不超过10的正整数。
输出:
第一行:只有一个数:实际所选课程的学分总数。
下面m行:从下到大所选择的课程。

这道题相对于上一道题不过是多了一种选择的方案输出而已,我们在转化为二叉树的基础上,愉快的再次建立一个bool数组ans[i]来表示这个点 i 是否被选中,然后再次一个DFS递归,如果当前的f[x][y]==f[Borther[x]][y]那么我们就继续递归DFS(Brother[x],y)就行,当前这个点x完全可以扔掉了!如果当前的if(f[x][y]==f[Brother[x]][i-1]+f[Child[x]][y-i]+Value[x]),那么我们就可以判定,当前点x一定是被选中的,然后分别对两个分支进行DFS,一个是儿子,一个是兄弟,然后就可以return了。
code:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,Value[600],Brother[600],x;
int f[600][600],Child[600];
bool ans[600];
void DFS(int x,int y)
{
if(f[x][y]>=0) return;
if(x==0||y==0)
{
f[x][y]=0;
return;
}
DFS(Brother[x],y);
for(int i=0;i<y;i++)
{
DFS(Brother[x],i);
DFS(Child[x],y-i-1);
int This=max(f[Brother[x]][y],f[x][y]);
f[x][y]=max(This,f[Brother[x]][i]+f[Child[x]][y-i-1]+Value[x]);
}
}
void Find(int x,int y)
{
if(x==0||y==0) return;
if(f[x][y]==f[Brother[x]][y])
Find(Brother[x],y);
else for(int i=1;i<=y;i++)
if(f[x][y]==f[Brother[x]][i-1]+f[Child[x]][y-i]+Value[x])
{
Find(Brother[x],i-1);
Find(Child[x],y-i);
ans[x]=true;
return;
}
}
int main()
{
memset(f,-1,sizeof(f));
memset(ans,0,sizeof(ans));
memset(Child,0,sizeof(Child));
memset(Brother,0,sizeof(Brother));
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>x>>Value[i];
Brother[i]=Child[x];
Child[x]=i;
}
DFS(Child[0],m);
cout<<f[Child[0]][m]<<endl;
Find(Child[0],m);
for(int i=1;i<=n;i++)
if(ans[i]) cout<<i<<endl;
return 0;
}



P1306河流
几乎整个Byteland 王国都被森林和河流所覆盖。小点的河汇聚到一起,形成了稍大点的河。就这样,所有的河水都汇聚并流进了一条大河,最后这条大河流进了大海。这条大河的入海口处有一个村庄——Bytetown。   
在Byteland国,有n个伐木的村庄,这些村庄都座落在河边。目前在Bytetown,有一个巨大的伐木场,它处理着全国砍下的所有木料。木料被砍下后,顺着河流而被运到Bytetown的伐木场。Byteland 的国王决定,为了减少运输木料的费用,再额外地建造k个伐木场。这k个伐木场将被建在其他村庄里。这些伐木场建造后,木料就不用都被送到Bytetown了,它们可以在 运输过程中第一个碰到的新伐木场被处理。显然,如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。 注:所有的河流都不会分叉,形成一棵树,根结点是Bytetown。   
国王的大臣计算出了每个村子每年要产多少木料,你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为:每一吨木料每千米1分钱。
   编一个程序:   
1.从文件读入村子的个数,另外要建设的伐木场的数目,每年每个村子产的木料的块数以及河流的描述。   
2.计算最小的运费并输出。
输入:
第一行包括两个数n(2<=n<=100),k(1<=k<=50,且k<=n)。n为村庄数,k为要建的伐木场的数目。除了Bytetown 外,每个村子依次被命名为 1,2,3……n,Bytetown被命名为0。
   接下来n行,每行3个整数: 
wi——每年 i 村子产的木料的块数。(0<=wi<=10000)
   vi——离 i 村子下游最近的村子。(即 i 村子的父结点)(0<=vi<=n)
   di——vi 到 i 的距离(千米)。(1<=di<=10000) 
  保证每年所有的木料流到bytetown 的运费不超过2000,000,000分
   50%的数据中n不超过20。
输出:
一行,最小的运费。

拿到这道题,其实我是想了好久的,尝试了各种各种DP的方法,但是一直GG,后来我突然想到了上一道题所用到的多叉树转二叉树的方法,然后用DFS遍历所有的点就可以了,最开始的时候我设置的状态f[i][j][k]表示的是对于当前节点i,一共使用j个工厂,然后k表示true或者false表示是否在当前进行建立工厂的最优值。但是发现又不行,因为距离是没有办法进行记录的,也就是说,这样的话记录下来没有办法确定木头的运输距离,也就是不知道距离它最近的工厂的位置,那么我们就更改一下状态的设置,我们表示出来f[i][j][k] 表示的是对于第i个点,距离他最近有工厂的点为j,其中选择建造了k个工厂。然后在DFS传参数的时候加上距离dis一项,然后我们就可以进行愉快的计算了。
然后对于一个点x,我们有两种选择方法,也就是第一种,自己建造工厂和自己用别人的工厂,那么我们就进行两次DP,然后在其中求出最优值,如果不在这里进行建造工厂的话枚举i从0到k,表示自己的儿子负担i个,然后兄弟们负担k-i个。
第二种,如果自己亲自进行建造工厂,那么枚举i从0到k-1,然后表示自己的孩子一共建造i个,然后自己的兄弟们负责建造k-i-1个(减去的1表示点x已经建造了一个工厂)
以后看到题想不清楚了,然后仔细推一推看看自己的状态设置是不是少了什么,是不是有些是没有用的,可以用更加强大的进行代替掉,然后就是参数的传递上需要进行传递什么,也要仔细考虑清楚的!
code:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,Child[200],Brother[200],len=0,x,Get;
int f[200][200][200],Weight[200],Distance[200];
bool vis[200];
int DFS(int x,int Root,int k,int dis)
{
if(x==-1||Root==-1) return 0;
if(f[x][Root][k]!=Get) return f[x][Root][k];
int LHH=f[x][Root][k];
for(int i=0;i<=k;i++) //如果不去建造伐木场
{
int First=DFS(Child[x],Root,i,dis+Distance[x]);
int Second=DFS(Brother[x],Root,k-i,dis);
int Value=(dis+Distance[x])*Weight[x];
LHH=min(LHH,First+Second+Value);
}
for(int i=0;i<k;i++) //如果选择建造伐木场
{
int First=DFS(Child[x],x,i,0);
int Second=DFS(Brother[x],Root,k-i-1,dis);
LHH=min(LHH,First+Second);
}
f[x][Root][k]=LHH;
return f[x][Root][k];
}
int main()
{
memset(Child,-1,sizeof(Child));
memset(vis,false,sizeof(vis));
memset(Brother,-1,sizeof(Brother));
memset(f,120,sizeof(f));
cin>>n>>m;
Get=f[0][0][0];
for(int i=1;i<=n;i++)
{
cin>>Weight[i]>>x>>Distance[i];
Brother[i]=Child[x];
Child[x]=i;
}
cout<<DFS(0,0,m,0)<<endl;
return 0;
}



P1512软件安装
现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M的计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。
但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件吗i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么他能够发挥的作用为0。
我们现在知道了软件之间的依赖关系:软件i依赖Di。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则Di=0,这是只要这个软件安装了,它就能正常工作。
读入:
第1行:N,M (0<=N<=100,0<=M<=500) 
第2行:W1,W2, … Wi, … ,Wn 
第3行:V1,V2, … Vi, … ,Vn 
第4行:D1,D2, … Di, … ,Dn
输出:
一个整数,代表最大价值。

这道题也是非常神奇的,一开始我是忽略掉了可能会出现环的情况,然后就开心的当成了选课,多叉转二叉,DFS直接开始深搜……
然后就只拿到了40分(省选题暴力搞到40分也是蛮不错的)
然后仔细想了想,发现的确可能出现环的情况,在左右思索无助的时候还是忍不住的看了题解QAQ,然后就来总结一发。
这道题的其实可以通过题目上的一个条件很清楚的看出来,因为题目上已经说过了,如果没有安装他的依赖软件,那么这个软件也是可以安装的,但是权值为0,所以这里就决定了这个图并不是寻常的树规……
对于出现环的关系,也就是1依赖2,2依赖1,那么出现这种情况的时候,我们就可以将2和1看作是一个点了,如果选择这个点那么就是肯定里面的1和2都选择,如果不选择这个点,那么权值和重量就全都是0了。
如果里面只选择1的话,结果就和全部都不选是一样的。那么我们就可以用Tarjan算法求出所有的联通分量,然后将所有的联通分量当成一个点,然后重新建造一个二叉树,在重新建造的二叉树上进行DP,状态设置就是f[i][j]表示对于节点i在承受j重量下,所能达到的最大权值。(变量声明的有些多QAQ)
code:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
struct Edge
{
int Next;
int Point;
}a[200];
int Value[200],Weight[200],n,m,len=0,This;
int Father,Link_First[200],f[200][600],top=0;
int ind=0,low[200],dfn[200],tot=0,Stack[200];
int Belong[200],Avalue[200],Aweight[200];
int Link_Second[200],Child[200],Brother[200];
bool Vis[200],Get[200],Find[200][600];
void Tarjan(int x)
{
int This=0;
low[x]=dfn[x]=++ind;
Stack[++top]=x;
Vis[x]=true;
for(int i=Link_First[x];i;i=a[i].Next)
{
int y=a[i].Point;
if(!dfn[y])
{
Tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(Vis[y])
low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x])
{
tot++;//找到一个联通分量缩成一个点
while(This!=x)
{
This=Stack[top--];
Vis[This]=false;
Belong[This]=tot;
Avalue[tot]+=Value[This];
Aweight[tot]+=Weight[This];
}
}
}
void Rebuild()//重新建为二叉树
{
int Cut=0;
for(int x=1;x<=n;x++)
for(int i=Link_First[x];i;i=a[i].Next)
if(Belong[a[i].Point]!=Belong[x])
{
This=a[i].Point;
Get[Belong[This]]=true;
Brother[Belong[This]]=Child[Belong[x]];
Child[Belong[x]]=Belong[This];
}
}
int DFS(int x,int dis)
{
if(dis<=0||x<0) return 0;
if(Find[x][dis]==true) return f[x][dis];
Find[x][dis]=true;
for(int i=0;i<=dis-Aweight[x];i++)//如果装x
{
int First=DFS(Child[x],i)+Avalue[x];
int Second=DFS(Brother[x],dis-i-Aweight[x]);
f[x][dis]=max(f[x][dis],First+Second);
}
f[x][dis]=max(f[x][dis],DFS(Brother[x],dis));//不装x
return f[x][dis];
}
int main()
{
ios::sync_with_stdio(false);
memset(Find,false,sizeof(Find));
memset(Brother,-1,sizeof(Brother));
memset(Child,-1,sizeof(Child));
memset(Vis,false,sizeof(Vis));
memset(Get,false,sizeof(Get));
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>Weight[i];
for(int i=1;i<=n;i++)
cin>>Value[i];
for(int i=1;i<=n;i++)
{
cin>>Father;
a[i].Point=i;
a[i].Next=Link_First[Father];
Link_First[Father]=i;
}
for(int i=0;i<=n;i++)
if(!dfn[i]) Tarjan(i);//使用Tarjan算法缩点
Rebuild();
for(int i=1;i<=tot;i++)
if(Get[i]==false)//将形成环的点归为没有约束的点
{
Get[i]=true;
Brother[i]=Child[0];
Child[0]=i;
}
cout<<DFS(0,m)<<endl;
return 0;
}




  评论这张
 
阅读(62)| 评论(0)

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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