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

洛谷:P2585 [ZJOI2006]三色二叉树(树dp,提高+/省选-)

程序员文章站 2022-06-27 17:31:03
题目:分析:我总觉得紫书上见过类似的。最多的应该考虑四层。自己的想法太复杂:如最少的自己的想法是,首先明确只有这种情况才要染绿色。如果是有两个子节点,三种情况,父,两子分别为绿色。父为绿。则判断子的子。子为绿,则该子的 子的子,兄弟的子。妈耶,一直想着非绿色的两种颜色统一化,结果就是这么简单:不过我充分利用非绿色两种颜色统一化比题解时间应该少一半:代码:#includeusing namespace std;string s;vector&...

题目:

洛谷:P2585 [ZJOI2006]三色二叉树(树dp,提高+/省选-)

分析:我总觉得紫书上见过类似的。最多的应该考虑四层。

自己的想法太复杂:如最少的自己的想法是,首先明确只有这种情况才要染绿色。

如果是有两个子节点,三种情况,父,两子分别为绿色。

父为绿。则判断子的子。

子为绿,则该子的 子的子,兄弟的子。

妈耶,一直想着非绿色的两种颜色统一化,结果就是这么简单:不过我充分利用非绿色两种颜色统一化比题解时间应该少一半:

洛谷:P2585 [ZJOI2006]三色二叉树(树dp,提高+/省选-)

代码:

#include<bits/stdc++.h>
using namespace std;
string s;
vector<vector<int> > vv;
int f_tree(int &x)
{//初始化树。 
 if(s[x]=='0')
 {
  return x;
 }
 if(s[x]=='2'){
  int c=x;
  x++;
  vv[c].push_back(f_tree(x));
  x++;
  vv[c].push_back(f_tree(x));
  return c;
 }
 if(s[x]=='1'){
  int c=x;
  x++;
  vv[c].push_back(f_tree(x));
  return c;
 }
}
long long A1[500005][3];
long long A2[500005][3];
long long f1(int x,int y)
{
 if(A1[x][y]!=-1) return A1[x][y];
 if(y==0)
 {
  if(vv[x].size()==0)
  {
   A1[x][y]=1;
   return A1[x][y]; 
  }
  if(vv[x].size()==1)
  {
   A1[x][y]=f1(vv[x][0],1)+1;
   A1[vv[x][0]][2]=A1[vv[x][0]][1];
   return A1[x][y]; 
  }
  if(vv[x].size()==2)
  {
   A1[x][y]=f1(vv[x][0],1)+f1(vv[x][1],1)+1;
   A1[vv[x][0]][2]=A1[vv[x][0]][1];
   A1[vv[x][1]][2]=A1[vv[x][1]][1];
   return A1[x][y]; 
  }
 }
 if(y==1)
 {
  if(vv[x].size()==0)
  {
   A1[x][y]=0;
   A1[x][2]=A1[x][y];
   return A1[x][y]; 
  }
  if(vv[x].size()==1)
  {
   A1[x][y]=max(f1(vv[x][0],2),f1(vv[x][0],0));
   A1[vv[x][0]][1]=A1[vv[x][0]][2];
   return A1[x][y]; 
  }
  if(vv[x].size()==2)
  {
   A1[x][y]=max(f1(vv[x][0],0)+f1(vv[x][1],2),f1(vv[x][0],2)+f1(vv[x][1],0));
   A1[vv[x][0]][1]=A1[vv[x][0]][2];
   A1[vv[x][1]][1]=A1[vv[x][1]][2];
   return A1[x][y]; 
  }
 }
 if(y==2)
 {
  if(vv[x].size()==0)
  {
   A1[x][y]=0;
   A1[x][1]=A1[x][y];
   return A1[x][y]; 
  }
  if(vv[x].size()==1)
  {
   A1[x][y]=max(f1(vv[x][0],1),f1(vv[x][0],0));
   A1[vv[x][0]][2]=A1[vv[x][0]][1];
   return A1[x][y]; 
  }
  if(vv[x].size()==2)
  {
   A1[x][y]=max(f1(vv[x][0],0)+f1(vv[x][1],1),f1(vv[x][0],1)+f1(vv[x][1],0));
   A1[vv[x][0]][2]=A1[vv[x][0]][1];
   A1[vv[x][1]][2]=A1[vv[x][1]][1];
   return A1[x][y];
  }
 }
}
long long f2(int x,int y)
{
 if(A1[x][y]!=-1) return A1[x][y];
 A1[x][y]=1<<30;
 if(y==0)
 {
  if(vv[x].size()==0)
  {
   A1[x][y]=1;
   return A1[x][y]; 
  }
  if(vv[x].size()==1)
  {
   A1[x][y]=f2(vv[x][0],1)+1;
   A1[vv[x][0]][2]=A1[vv[x][0]][1];
   return A1[x][y]; 
  }
  if(vv[x].size()==2)
  {
   A1[x][y]=f2(vv[x][0],1)+f2(vv[x][1],1)+1;
   A1[vv[x][0]][2]=A1[vv[x][0]][1];
   A1[vv[x][1]][2]=A1[vv[x][1]][1];
   return A1[x][y]; 
  }
 }
 if(y==1)
 {
  if(vv[x].size()==0)
  {
   A1[x][y]=0;
   A1[x][2]=A1[x][y];
   return A1[x][y]; 
  }
  if(vv[x].size()==1)
  {
   A1[x][y]=min(f2(vv[x][0],2),f2(vv[x][0],0));
   A1[vv[x][0]][1]=A1[vv[x][0]][2];
   return A1[x][y]; 
  }
  if(vv[x].size()==2)
  {
   A1[x][y]=min(f2(vv[x][0],0)+f2(vv[x][1],2),f2(vv[x][0],2)+f2(vv[x][1],0));
   A1[vv[x][0]][1]=A1[vv[x][0]][2];
   A1[vv[x][1]][1]=A1[vv[x][1]][2];
   return A1[x][y];
  }
 }
 if(y==2)
 {
  if(vv[x].size()==0)
  {
   A1[x][y]=0;
   A1[x][1]=A1[x][y];
   return A1[x][y]; 
  }
  if(vv[x].size()==1)
  {
   A1[x][y]=min(f2(vv[x][0],1),f2(vv[x][0],0));
   A1[vv[x][0]][2]=A1[vv[x][0]][1];
   return A1[x][y]; 
  }
  if(vv[x].size()==2)
  {
   A1[x][y]=min(f2(vv[x][0],0)+f2(vv[x][1],1),f2(vv[x][0],1)+f2(vv[x][1],0));
   A1[vv[x][0]][2]=A1[vv[x][0]][1];
   A1[vv[x][1]][2]=A1[vv[x][1]][1];
   return A1[x][y];
  }
 }
}
int main()
{
 cin>>s;
 vector<int> v;
 for(int i=0;i<s.size();i++) vv.push_back(v);
 memset(A1,-1,sizeof(A1));
 int c=0;
 f_tree(c);
 cout<<max(f1(0,0),f1(0,1))<<' ';
 memset(A1,-1,sizeof(A1));
 cout<<min(f2(0,0),f2(0,1));
}

本文地址:https://blog.csdn.net/weixin_42721412/article/details/107597262

相关标签: 动态规划