传送门!
简要题意:有棵树,每个节点有个权值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
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&＃61;x;i<&＃61;y;&＃43;&＃43;i)
#define my(i,x,y) for(rg int i&＃61;x;i>&＃61;y;--i)
const int N&＃61;100&＃43;2,K&＃61;50&＃43;2;
int n,k,w[N],stck_top,stck[N],dis[N];
ll f[N][K][N][2];
vector
il int read()
{
rg char ch&＃61;gc;rg int x&＃61;0;rg bool y&＃61;1;
while(ch!&＃61;&＃39;-&＃39; && (ch>&＃39;9&＃39; || ch<&＃39;0&＃39;))ch&＃61;gc;
if(ch&＃61;&＃61;&＃39;-&＃39;)ch&＃61;gc,y&＃61;0;
while(ch>&＃61;&＃39;0&＃39; && ch<&＃61;&＃39;9&＃39;)x&＃61;(x<<1)&＃43;(x<<3)&＃43;(ch^&＃39;0&＃39;),ch&＃61;gc;
return y?x:-x;
}
il void dfs(int nw)
{
stck[&＃43;&＃43;stck_top]&＃61;nw;
int sz&＃61;son[nw].size();
rp(i,0,sz-1)
{
dis[son[nw][i].fr]&＃61;dis[nw]&＃43;son[nw][i].sc;dfs(son[nw][i].fr);
my(j,stck_top,1)
{
my(p,k,0)
{
f[nw][p][stck[j]][0]&＃43;&＃61;f[son[nw][i].fr][0][stck[j]][0];
f[nw][p][stck[j]][1]&＃43;&＃61;f[son[nw][i].fr][0][nw][0];
my(q,p,0)
{
f[nw][p][stck[j]][0]&＃61;min(f[nw][p][stck[j]][0],f[son[nw][i].fr][q][stck[j]][0]&＃43;f[nw][p-q][stck[j]][0]),
f[nw][p][stck[j]][1]&＃61;min(f[nw][p][stck[j]][1],f[son[nw][i].fr][q][nw][0]&＃43;f[nw][p-q][stck[j]][1]);
}
}
}
}
rp(i,1,stck_top)
{
my(j,k,0)
if(j)f[nw][j][stck[i]][0]&＃61;min(f[nw][j-1][stck[i]][1],f[nw][j][stck[i]][0]&＃43;w[nw]*(dis[nw]-dis[stck[i]]));
else f[nw][j][stck[i]][0]&＃43;&＃61;w[nw]*(dis[nw]-dis[stck[i]]);
}
--stck_top;
return;
}
int main()
{
// freopen("riv.in","r",stdin);freopen("riv.out","w",stdout);
n&＃61;read();k&＃61;read();
rp(i,1,n){w[i]&＃61;read();int fa&＃61;read(),dis&＃61;read();son[fa].push_back(mp(i,dis));}
dfs(0);printf("%lld\n",f[0][k][0][0]);
return 0;
}
顺便港下,这题有个双倍经验
都差不多只是还要建棵trie树就好了,over
等下把那题代码也放上来吼QwQ
#include
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&＃61;x;i<&＃61;y;&＃43;&＃43;i)
#define my(i,x,y) for(rg int i&＃61;x;i>&＃61;y;--i)
const int N&＃61;500&＃43;2,K&＃61;10&＃43;2;
int n,k,stck_top,stck[N],dis[N],nod_cnt;
ll f[N][K][N][2],as;
struct node{int to[10],wei;}tr[N*100];
il int read()
{
rg char ch&＃61;gc;rg int x&＃61;0;rg bool y&＃61;1;
while(ch!&＃61;&＃39;-&＃39; && (ch>&＃39;9&＃39; || ch<&＃39;0&＃39;))ch&＃61;gc;
if(ch&＃61;&＃61;&＃39;-&＃39;)ch&＃61;gc,y&＃61;0;
while(ch>&＃61;&＃39;0&＃39; && ch<&＃61;&＃39;9&＃39;)x&＃61;(x<<1)&＃43;(x<<3)&＃43;(ch^&＃39;0&＃39;),ch&＃61;gc;
return y?x:-x;
}
il void insert(string str,ll wei)
{
ll lth&＃61;str.length(),nw&＃61;0;
rp(i,0,lth-1)
{
if(!tr[nw].to[str[i]^&＃39;0&＃39;])tr[nw].to[str[i]^&＃39;0&＃39;]&＃61;&＃43;&＃43;nod_cnt;
nw&＃61;tr[nw].to[str[i]^&＃39;0&＃39;];tr[nw].wei&＃43;&＃61;wei;
}
}
il void dfs(int nw)
{
stck[&＃43;&＃43;stck_top]&＃61;nw;
rp(i,0,9)
{
if(!tr[nw].to[i])continue;dis[tr[nw].to[i]]&＃61;dis[nw]&＃43;1;dfs(tr[nw].to[i]);
my(j,stck_top,1)
my(p,k,0)
my(q,p,0)
f[nw][p][stck[j]][0]&＃61;max(f[nw][p][stck[j]][0],f[tr[nw].to[i]][q][stck[j]][0]&＃43;f[nw][p-q][stck[j]][0]),
f[nw][p][stck[j]][1]&＃61;max(f[nw][p][stck[j]][1],f[tr[nw].to[i]][q][nw][0]&＃43;f[nw][p-q][stck[j]][1]);
}
rp(i,1,stck_top)
my(j,k,0)
if(j)f[nw][j][stck[i]][0]&＃61;max(f[nw][j-1][stck[i]][1]&＃43;tr[nw].wei*(dis[nw]-dis[stck[i]]),f[nw][j][stck[i]][0]);
--stck_top;
return;
}
int main()
{
// freopen("sd.in","r",stdin);freopen("sd.out","w",stdout);
n&＃61;read();k&＃61;read();rp(i,1,n){string str;cin>>str;ll wei&＃61;read();insert(str,wei);as&＃43;&＃61;str.length()*wei;}
dfs(0);printf("%lld\n",as-f[0][k][0][0]);
return 0;
}
京公网安备 11010802041100号