BZOJ1812 [IOI2005]river
2024-09-12 11:09:17
很常规的一道树规,转为左儿子右兄弟。
然后$f[node][anc][K]$表示在node节点上,最近的有贡献祖先在anc上,在node的儿子和兄弟上有k个有贡献节点的最优值。
然后得出以下转移方程。
$f[node][anc][K]=min\{f[son[node]][anc][k]+f[bro[node]][anc][K-k]\}+Value[node]*(dis[node]-dis[anc])$无贡献
$f[node][anc][K]=min\{f[son[node]][node][k]+f[bro[node]][anc][K-1-k]\}$ 有贡献
下面是代码实现:
//BZOJ 1812 //by Cydiater //2016.9.5 #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <ctime> #include <cmath> #include <iomanip> using namespace std; #define ll long long #define up(i,j,n) for(int i=j;i<=n;i++) #define down(i,j,n) for(int i=j;i>=n;i--) ; const int oo=0x3f3f3f3f; inline int read(){ ,f=; ;ch=getchar();} +ch-';ch=getchar();} return x*f; } ,fa[MAXN],f[MAXN][MAXN][MAXN],pre_fa[MAXN]; struct edge{ int y,next,v; }e[MAXN<<]; namespace solution{ inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;} void dfs(int node){ for(int i=LINK[node];i;i=e[i].next){ dis[e[i].y]=dis[node]+e[i].v; dfs(e[i].y); } } void init(){ N=read();K=read(); pre_fa[]=-; up(i,,N){ Value[i]=read();int y=read(),v=read(); pre_fa[i]=y; insert(y,i,v); } dfs();dis[]=; } void build(int node,int father){ int tmp=LINK[node];son[node]=e[tmp].y;fa[node]=father; if(tmp)build(e[tmp].y,node);node=e[tmp].y; for(int i=e[tmp].next;i;i=e[i].next){ bro[node]=e[i].y;build(e[i].y,node); node=e[i].y; } } void TreeDP(int node){ if(son[node])TreeDP(son[node]); if(bro[node])TreeDP(bro[node]); int father=pre_fa[node]; ){ up(lim,,K)up(k,,lim){ int tmp=Value[node]*(dis[node]-dis[father]); if(son[node])tmp+=f[son[node]][father][k]; if(bro[node])tmp+=f[bro[node]][father][lim-k]; f[node][father][lim]=min(f[node][father][lim],tmp); } up(lim,,K)up(k,,lim){ ; ]; if(bro[node])tmp+=f[bro[node]][father][lim-k]; f[node][father][lim]=min(f[node][father][lim],tmp); } father=pre_fa[father]; } ){ father=; up(lim,,K)up(k,,lim){ ; if(son[node])tmp+=f[son[node]][father][k]; if(bro[node])tmp+=f[bro[node]][father][lim-k]; f[node][father][lim]=min(f[node][father][lim],tmp); } } } void slove(){ build(,-); memset(f,0x3f,sizeof(f)); TreeDP(); printf(][][K]); } } int main(){ //freopen("input.in","r",stdin); using namespace solution; init(); slove(); ; }
最新文章
- 【BZOJ-4653】区间 线段树 + 排序 + 离散化
- uva 1660 &; poj 1966(点连通度)
- IOS之资源收集--很好的github网址
- Implement Stack using Queues
- java笔试题整理
- 【好文要转】Python:模拟登录以获取新浪微博OAuth的code参数值
- 浅谈Oracle函数返回Table集合
- 【开源项目12】Retrofit – Java(Android) 的REST 接口封装类库
- 基于Jquery+Ajax+Json+高效分页
- <;转>;DNS服务系列之二:DNS区域传送漏洞的安全案例
- 由于 UNION ALL Chinese_PRC_CI_AS”之间的排序规则冲突,值的排序规则未经解析
- Javascript是单线程的深入分析(转)
- 集成学习之Boosting —— AdaBoost原理
- DataCleaner(4.5)第二章
- 【Mysql】—— 索引的分类
- 事务 c#
- L246‘’
- 品味性能之道<;九>;:利用Loadrunner编写socket性能测试脚本简述
- 对SpringDAO层支持的总结
- 一步一步学习IdentityServer3 (5)
热门文章
- Bootstrap系列 -- 3. 段落
- 20160220 - JavaScript for OS X Automation 调试技巧
- 转一篇Unity客户端与Java服务器的通信
- Java 增强型的for循环 for each
- Php 安装 curl
- Golang操作数据库
- difference between append and appendTo
- fatal: Not a valid object name: &#39;master&#39;.
- Entity Framework Code First (一)Conventions
- Java栈的实例模拟