- 1、本文档共42页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
树形DP
二叉苹果树(ural 1108)
题目意思:
有一棵苹果树,苹果树的是一棵二叉树,共N个节点,树节点编号为1~N,编号为1的节点为树根,边可理解为树的分枝,每个分支都长着若干个苹果,现在要要求减去若干个分支,保留M个分支,要求这M个分支的苹果数量最多。
输入:
N M
接下来的N-1行是树的边,和该边的苹果数N and M (1 ≤ M N; 1 N ≤ 100)
输出:
剩余苹果的最大数量。
input
5 2
1 3 1
1 4 10
2 3 20
3 5 20
output
21
算法:
删除了某个分支,那么这个分支下的子分支也同时删除。
保留M个分支,也就是删除N-M-1个分支。剩余的最多苹果数=总苹果数-剪掉的苹果数。
注意本题给的边并没有按照树根--树叶的形式来给,也没有按照树的顺序给出边。本来想一个节点对应一个分支长着的苹果数量,cost[v]就表示v这个节点的苹果数,可以这样做,但是在输入的时候,不知道这个苹果数量是那个节点的,因为不知道哪个是哪个的子结点。所以用了无向图和苹果数加到边上去。
我的解法中:这题的树状DP的整体思想个pku3345是一样的。
有一些不一样的地方要注意一下:
本程序其实不仅仅针对二叉树,可以是任意的树,删除任意个分支都有算。
#includeiostream
#includevector
#includelimits
using namespace std;
#define MN 110
int f[2*MN],p[MN],tmp[MN];
int N,M;
bool visit[MN];
struct NODE
{
int val;
int cost;
};
vectorNODEG[MN];
inline int max(int a,int b)
{
return ab?a:b;
}
inline int min(int a,int b)
{
return ab?a:b;
}
void my_clear()
{
int i;
for(i=0;i=N;i++)
{
G[i].clear();
}
memset(visit,false,sizeof(visit));
}
int DP(int v,int from)
{
visit[v]=true;
int i,j,k,s,w,last,now;
s=G[v].size();
if(s==1) //这边不再是s==0
{
p[0]=0;
return 1;
}
last=0;
f[from]=0;
for(i=0;is;i++)
{
w=G[v][i].val;
if(visit[w]==true)
continue;
now=DP(w,from+last+1);
p[now]=p[now-1]+G[v][i].cost; //这边不要漏,把节点w也给删除
for(j=0;j=last+now;j++)
tmp[j]=INT_MAX;
for(j=0;j=last;j++)
{
for(k=0;k=now;k++)
{
tmp[j+k]=min(tmp[j+k],f[from+j]+p[k]);
}
}
last+=now;
for(j=0;j=last;j++)
{
f[from+j]=tmp[j];
}
}
for(i=0;i=last;i++)
p[i]=f[i+from];
last++; //加上自身节点
return last;
}
int main()
{
int i,a,b,sum,c;
NODE tmp;
while(scanf(%d%d,N,M)!=EOF)
{
sum=0;
my_clear();
for(i=1;iN;i++)
{
scanf(%d%d%d,a,b,c);
tmp.cost=c;
tmp.val=b;
G[a].push_back(tmp);
tmp.val=a;
G[b].push_back(tmp);
sum+=c;
}
DP(1,0);
printf(%d\n,sum-f[N-M-1]);
}
return 0;
}
有限电视网络(pku1155 TELE)
题目描述:
有一个电视台要用电视网络转播节目。这种电视网络是一树,树的节点为中转站或者用户。树节点的编号为1~N,其中1为总站,2~(N-M)为中转站,(总站和中转站统称为转发站)N-M+1~N为用户,电视节目从一个地方传到另一个地方都要费用,同时每一个用户愿意出相应的钱来付电视节目。
您可能关注的文档
- 数学分析8.2 可积准则详解(二)1.ppt
- 初三物理电磁铁[整理]新课标1.ppt
- 数字图像处理_(整理后的试题).pdf
- 隧道设计理论讲义1.ppt
- 第02章 货币市场(讲义).ppt
- 第5章-弯曲内力例题详解1.ppt
- 田间试验统计第二章资料的整理与描述.ppt
- 第10章 数据的收集、整理与描述期末复习.ppt
- 第14章_变形观测的成果整理与分析.pdf
- 统计学 第3章 数据整理和频数分布.ppt
- 浙江省金华市曙光学校2024_2025学年高一历史上学期期中试题.doc
- 河南省新乡市卫辉市高级中学2024_2025学年高一历史下学期第一次调研考试试题含解析.doc
- 江苏省苏州新草桥中学2024_2025学年高一历史下学期6月月考试题.doc
- 广东省广州市广东实验中学2025届高三生物下学期线上考试试题含解析.doc
- 广东省廉江市实验学校2024_2025学年高二历史下学期第七次限时训练试题A班.doc
- 通史版2025届高考历史大一轮总复习课时作业8“百家争鸣”和汉代儒学成为正统思想含解析.doc
- 陕西省铜川市一中2025届高三生物八模试题含解析.doc
- 河北省衡水市桃城区第十四中学2024_2025学年高一历史下学期期末考试试题.doc
- 江西省宜春市2024_2025学年高一化学下学期第七次月考试题4月.doc
- 陕西省宝鸡市金台区2024_2025学年高二政治上学期期中试题.doc
文档评论(0)