洛谷:P2015 二叉苹果树(dp树,普及/提高-)
程序员文章站
2022-03-05 14:23:54
题目:分析:看错题目,要删几个!。。。减一下就欧克啦。但是,减去一个不单单是减去了一个啊。是减去了一串啊!代码:#includeusing namespace std;int m,n;int A[101][2];//存放子树。vector >vv; int B[101][101];//存放树上的苹果long long D[101][101];int t[101];//存放个数。map
题目:
分析:看错题目,要删几个!。。。减一下就欧克啦。但是,减去一个不单单是减去了一个啊。是减去了一串啊!
代码:
#include<bits/stdc++.h>
using namespace std;
int m,n;
int A[101][2];//存放子树。
vector<vector<int> >vv;
int B[101][101];//存放树上的苹果
long long D[101][101];
int t[101];//存放个数。
map<int,int> mm;
long long f(int x,int y)
{
if(D[x][y]!=-1) return D[x][y];
//特殊。
if(y==0)
{//统计
if(A[x][0]==-1) return 0;
D[x][y]=B[x][A[x][0]]+f(A[x][0],y)+B[x][A[x][1]]+f(A[x][1],y);
return D[x][y];
}
if(A[x][0]==-1||t[x]<y) return -(1<<30);
if(t[x]==y) return 0;
D[x][y]=0;
//都不
long long a=-1;
for(int i=0;i<=y;i++) a=max(a,B[x][A[x][1]]+B[x][A[x][0]]+f(A[x][0],i)+f(A[x][1],y-i));
//左右
long long b=-1;
if(y>=1+t[A[x][0]])
b=B[x][A[x][1]]+f(A[x][1],y-1-t[A[x][0]]);
if(y>=1+t[A[x][1]])
b=max(b,B[x][A[x][0]]+f(A[x][0],y-1-t[A[x][1]]));
D[x][y]=max(a,b);
if(D[x][y]<0) D[x][y]=-(1<<30);
return D[x][y];
}
void f2(int x)
{
mm[x]=1;
for(int i=0;i<vv[x].size();i++)
{
if(mm[vv[x][i]]==0)
{
if(A[x][0]==-1){
A[x][0]=vv[x][i];
}
else{
A[x][1]=vv[x][i];
}
f2(vv[x][i]);
}
}
}
int f3(int x)
{
if(t[x]!=0) return t[x];
if(A[x][0]==-1) {
t[x]=0;
return 0;
}
t[x]=2+f3(A[x][1])+f3(A[x][0]);
return t[x];
}
int main()
{
cin>>m>>n;
memset(D,-1,sizeof(D));
memset(A,-1,sizeof(A));
memset(t,0,sizeof(t));
vector<int> v;
for(int i=0;i<=m;i++) vv.push_back(v);
for(int i=1;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
B[a][b]=B[b][a]=c;
vv[a].push_back(b);
vv[b].push_back(a);
}
f2(1);
f3(1);
//long long c=0;
cout<<f(1,m-1-n);
}
本文地址:https://blog.csdn.net/weixin_42721412/article/details/107593546
上一篇: 最短路