[vijos1880]选课<树形dp>
2024-10-08 23:20:04
题目链接:https://www.vijos.org/p/1180
这是一道树形dp的裸题,唯一的有意思的地方就是用到了多叉树转二叉树
然后本蒟蒻写这一道水题就是因为以前知道这个知识点但是没有怎么去实现,所以就写了这一道题来练一练手
将这道题的多叉树转换成二叉树后,接着就是状态转移方程了
我们先定义数组dp[i][j]表示第i门课,还可以选j门
然后我们可以想到,第i门课我们可以不选,如果不选,就不能去找i的左儿子,但是可以找i的右儿子,即i的右儿子(兄弟)选了j门
加入选了i,那么状态来源就是i的儿子和兄弟课程一共选了j-1门(假设儿子一方选了k门,则兄弟选了j-1-k门)
然后就可以退出我们可爱的动态转移方程式了
dp[i][j]=max{dp[i.rc][j],dp[i.lc][k]+dp[i.rc][j-1-k]+i.val};
动态方程出来了,那程序也就自然而然得出来了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<queue>
#define maxn 2005
using namespace std; struct node{
int lc,rc,val;
}e[maxn*]; int n,m;
int dp[maxn][maxn];//第i门课,已经选了j门 void tree(int x,int y)
{
if(dp[x][y]!=)return;
if(e[x].rc!=)tree(e[x].rc,y);//不取自己,取兄弟
int tmp=dp[e[x].rc][y];
for(int i=;i<y;i++)//自己选了,然后还有y-1门可以选,分别给左儿子和右儿子
{
if(e[x].lc!=)tree(e[x].lc,i);
if(e[x].rc!=)tree(e[x].rc,y--i);
tmp=max(tmp,dp[e[x].lc][i]+dp[e[x].rc][y-i-]+e[x].val);
}
dp[x][y]=tmp;
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
int b,c;
scanf("%d%d",&b,&c);//b为i的父亲
e[i].val=c;
e[i].rc=e[b].lc;//b的儿子是i的兄弟
e[b].lc=i;//i是b的儿子
}
tree(e[].lc,m); printf("%d",dp[e[].lc][m]);
}
最新文章
- div自适应高度
- svg.js教程及使用手册详解(二)
- React Native环境配置和简单使用
- 模拟namenode崩溃,使用secondarynamenode恢复
- NEERC 2013, Eastern subregional contest
- JS的文本编辑框jwysiwyg-0.6
- linux 标准 GPIO 操作
- ajaxfileUpload ajax 上传图片使用
- android4.0 HttpClient 以后不能在主线程发起网络请求
- 网易云课堂_C语言程序设计进阶_第5周:链表
- VS2012的变态优化,双循环变单循环
- jq,js简单实现类似Angular.js数据绑定效果
- 43. Multiply Strings字符串相乘
- (4).NET CORE微服务 Micro-Service ---- Consul服务发现和消费
- 9. Oracle DataGuard的介绍
- 洗礼灵魂,修炼python(16)--列表进阶话题—>;上节作业讲解+copy模块,浅拷贝,深拷贝
- SpringMVC @SessionAttributes 使用
- Jetson tk1 hash sum mismatch
- 【转】Spotlight实时监控Windows Server 2008
- showdoc 开源在线api&;&;技术文档管理工具
热门文章
- git工作中常用操作总结
- 【echarts3】 折线图我踩过的那些坑 (tooltip 设置,line 单个点/散点不显示问题)
- 基于springcloud搭建项目-公共篇(二)
- 编译 ijg JPEG V8 库 GIF 库
- Ajax上传数据和上传文件(三种方式)
- AspNetCore3.1源码解析_2_Hsts中间件
- vue+django+webpack搭建
- Python多线程的事件监控
- Python-hashlib、OS、Random、sys、zipfile模块
- 升级 nop 4.1 Incorrect syntax near &#39;OFFSET&#39;. Invalid usage of the option NEXT in the FETCH statement.