洛谷P3354 Riv河流 [IOI2005] 树型dp
2024-10-19 03:25:53
正解:树型dp
解题报告:
简要题意:有棵树,每个节点有个权值w,要求选k个节点,最大化∑dis*w,其中如果某个节点到根的路径上选了别的节点,dis指的是到达那个节点的距离
首先这个一看就是个树型dp嘛,关键是怎么设状态
首先肯定是想到设f[i][j]:以i为根的子树中选了j个点
这个时候发现布星昂,这么设的时候我们不能得到对于到根的路径上的点的贡献鸭,所以就考虑加一维
所以f[i][j][k]:以i为根的子树中选了j个点,最近祖先的距离为k的最大代价
然后直接转移就好
对了还要说一个就,我这里有转点儿题意?就它是问最小化花费,然后我写题解的时候是转化成的tot-max∑
但实际实现的时候我是直着写的就是说直接最小化花费打的QAQ
差不多差不多QAQ
然后我发现我现在码力是真的弱,,,,我知道这题正解了,还是个dp题,然后打了2h?我原地自杀了要,,,
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define fr first
#define sc second
#define rg register
#define gc getchar()
#define ll long long
#define mp make_pair
#define rp(i,x,y) for(rg int i=x;i<=y;++i)
#define my(i,x,y) for(rg int i=x;i>=y;--i) const int N=+,K=+;
int n,k,w[N],stck_top,stck[N],dis[N];
ll f[N][K][N][];
vector< pair<int,int> >son[N]; il int read()
{
rg char ch=gc;rg int x=;rg bool y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il void dfs(int nw)
{
stck[++stck_top]=nw;
int sz=son[nw].size();
rp(i,,sz-)
{
dis[son[nw][i].fr]=dis[nw]+son[nw][i].sc;dfs(son[nw][i].fr);
my(j,stck_top,)
{
my(p,k,)
{
f[nw][p][stck[j]][]+=f[son[nw][i].fr][][stck[j]][];
f[nw][p][stck[j]][]+=f[son[nw][i].fr][][nw][];
my(q,p,)
{
f[nw][p][stck[j]][]=min(f[nw][p][stck[j]][],f[son[nw][i].fr][q][stck[j]][]+f[nw][p-q][stck[j]][]),
f[nw][p][stck[j]][]=min(f[nw][p][stck[j]][],f[son[nw][i].fr][q][nw][]+f[nw][p-q][stck[j]][]);
}
}
}
}
rp(i,,stck_top)
{
my(j,k,)
if(j)f[nw][j][stck[i]][]=min(f[nw][j-][stck[i]][],f[nw][j][stck[i]][]+w[nw]*(dis[nw]-dis[stck[i]]));
else f[nw][j][stck[i]][]+=w[nw]*(dis[nw]-dis[stck[i]]);
}
--stck_top;
return;
} int main()
{
// freopen("riv.in","r",stdin);freopen("riv.out","w",stdout);
n=read();k=read();
rp(i,,n){w[i]=read();int fa=read(),dis=read();son[fa].push_back(mp(i,dis));}
dfs();printf("%lld\n",f[][k][][]);
return ;
}
最后放下代码QAQ
顺便港下,这题有个双倍经验
都差不多只是还要建棵trie树就好了,over
等下把那题代码也放上来吼QwQ
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define fr first
#define sc second
#define rg register
#define gc getchar()
#define ll long long
#define mp make_pair
#define rp(i,x,y) for(rg int i=x;i<=y;++i)
#define my(i,x,y) for(rg int i=x;i>=y;--i) const int N=+,K=+;
int n,k,stck_top,stck[N],dis[N],nod_cnt;
ll f[N][K][N][],as;
struct node{int to[],wei;}tr[N*]; il int read()
{
rg char ch=gc;rg int x=;rg bool y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il void insert(string str,ll wei)
{
ll lth=str.length(),nw=;
rp(i,,lth-)
{
if(!tr[nw].to[str[i]^''])tr[nw].to[str[i]^'']=++nod_cnt;
nw=tr[nw].to[str[i]^''];tr[nw].wei+=wei;
}
}
il void dfs(int nw)
{
stck[++stck_top]=nw;
rp(i,,)
{
if(!tr[nw].to[i])continue;dis[tr[nw].to[i]]=dis[nw]+;dfs(tr[nw].to[i]);
my(j,stck_top,)
my(p,k,)
my(q,p,)
f[nw][p][stck[j]][]=max(f[nw][p][stck[j]][],f[tr[nw].to[i]][q][stck[j]][]+f[nw][p-q][stck[j]][]),
f[nw][p][stck[j]][]=max(f[nw][p][stck[j]][],f[tr[nw].to[i]][q][nw][]+f[nw][p-q][stck[j]][]);
}
rp(i,,stck_top)
my(j,k,)
if(j)f[nw][j][stck[i]][]=max(f[nw][j-][stck[i]][]+tr[nw].wei*(dis[nw]-dis[stck[i]]),f[nw][j][stck[i]][]);
--stck_top;
return;
} int main()
{
// freopen("sd.in","r",stdin);freopen("sd.out","w",stdout);
n=read();k=read();rp(i,,n){string str;cin>>str;ll wei=read();insert(str,wei);as+=str.length()*wei;}
dfs();printf("%lld\n",as-f[][k][][]);
return ;
}
因为一些,奇怪的问题,我发现我顺着做布星,按上面那个as-=max的思路就欧克,,,
最新文章
- title与alt的区别
- Python处理JSON
- 转:JQuery.Ajax之错误调试帮助信息
- R绘图基础
- mormot THttpApiServer使用例子
- Selenium2学习-037-WebUI自动化实战实例-IE浏览器显示比例问题:org.openqa.selenium.remote.SessionNotFoundException: Unexpected error launching Internet Explorer. Browser zoom level was set to 94%. It should be set to 100%
- tomcat和mysql安装配置总结
- python 复杂表达式,以及表单的处理
- 对 Azure Backup 的常见配置问题进行故障排除
- mysql忘记密码的处理方式(整理非原创)
- onu-reg-unreg.vbs
- LoadRunner学习笔记(1)--异常处理方法
- Linux Shell脚本编程
- ubuntu 16.04下源码安装opencv3.4
- tp视图模板
- Kubernetes学习之路(二十)之K8S组件运行原理详解总结
- node+express实现文件上传功能
- APP性能测试中的几个重要概念
- 【Cf #502 F】The Neutral Zone
- Windows上建立、取消共享文件夹