题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1054
方法:一个节点选了,则其直接子节点可选可不选,一个节点没有选,则直接子节点必须选,所以建议状态转移方程设
F(P,0)为没有选择p点最少要用多少点,
F(P,1)为选择p点最少要用多少点
{
sum({F(S,1)|S是p的直接子节点});P为非叶子
F(P,0)=
0;P为叶子
},
{
sum({ min(F(S,1),F(S,0)) |S是p的直接子节点 })+1;P为非叶子
F(P,1)=
1;P为叶子
}
原来问题的解是min(F(root,1),F(root,0)).
注意这种输入方式如何确定root
代码:
#include <iostream>
#include <queue>
#include<algorithm>
using namespace std;
int n,m,MAX=1600;
bool map[1501][1501];
struct Arc
{
int vetex;
Arc* nextArc;
};
struct Node
{
int x;
int inDegree;
Arc* firstArc;
int layer;
int noChose;
int chose;
};
Node nodes[1501];
void createArc(int s,int e)
{
Arc* arc = (Arc*)malloc(sizeof(Arc));
arc->vetex=e;
if(nodes[s].firstArc==NULL)
arc->nextArc=NULL;
else
arc->nextArc=nodes[s].firstArc;
nodes[s].firstArc = arc;
}
int treeDP[2000][2];
int myMin(int x,int y)
{
return x>y ? y:x;
}
void treeDp(int root)
{
Arc* arc = nodes[root].firstArc;
int v,sonCount=0;
while(arc!=NULL)
{
v=arc->vetex;
treeDp(v);
nodes[root].noChose += nodes[v].chose;
nodes[root].chose += myMin(nodes[v].chose,nodes[v].noChose);
arc=arc->nextArc;
sonCount++;
}
if(sonCount == 0)
{
nodes[root].noChose = 0;
nodes[root].chose = 1;
}
}
void main()
{
while(scanf("%d",&n)!=EOF)
{
memset(treeDP,0,sizeof(treeDP));
for(int i=0;i<n;i++)
{
nodes[i].inDegree=0;
nodes[i].firstArc=NULL;
nodes[i].noChose = 0;
nodes[i].chose = 1;
}
for(int i=0;i<n;i++)
{
char str[20];
cin>>str;
int number=0,posLeft,count=0;
for(int i=0;i<::strlen(str);i++)
{
if(str[i]==':')
{
int seed =1;
for(int k =i-1;k>=0;k--)
{
number+=(seed*(str[k]-'0'));
seed*=10;
}
}
if(str[i]=='(')
posLeft=i;
if(str[i]==')')
{
int seed =1;
for(int k = i-1;k>posLeft;k--)
{
count+=(seed*(str[k]-'0'));
seed*=10;
}
}
}
nodes[number].x=number;
for(int y=0;y<count;y++)
{
int son;
cin>>son;
nodes[son].x=son;
nodes[son].inDegree++;
createArc(number,son);
}
}
for(int i=0;i<n;i++)
{
if(nodes[i].inDegree==0)
{
nodes[i].layer=0;
treeDp(i);
cout<<myMin(nodes[i].noChose,nodes[i].chose)<<endl;
break;
}
}
}
}
感想:入门水题