欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷: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

题目:

洛谷:P2015 二叉苹果树(dp树,普及/提高-)

分析:看错题目,要删几个!。。。减一下就欧克啦。但是,减去一个不单单是减去了一个啊。是减去了一串啊!

代码:

#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

相关标签: 动态规划