求最少放置数量
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1510;
int h[N], e[N], ne[N], idx;
int n;
int f[N][2];
// f[i,s]表示考虑以i为根节点的子树,根节点放( s == 1 )或者不放( s == 0 )且满足题目限制的最少放置数量;
int fa[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
f[u][0] = 0, f[u][1] = 1;
for (int i = h[u]; i != -1; i = ne[i])
{
int son = e[i];
dfs(son);
f[u][1] += min(f[son][1], f[son][0]);
f[u][0] += f[son][1];
}
}
signed main(void)
{
while (cin >> n)
{
memset(h, -1, sizeof(h));
idx = 0;
memset(f, 0, sizeof(f));
memset(fa, 0, sizeof(fa));
int root = -1;
for (int i = 1; i <= n; i++)
{
int father, cnt;
scanf("%lld:(%lld)", &father, &cnt);
father++;
for (int i = 1; i <= cnt; i++)
{
int son;
cin >> son;
son++;
add(father, son);
fa[son] = father;
}
}
for (int i = 1; i <= n; i++)
{
if (!fa[i])
{
root = i;
}
}
dfs(root);
cout << min(f[root][0], f[root][1]) << endl;
}
return 0;
}
求所有合法方案数
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1510;
int h[N], e[N], ne[N], idx;
int n;
int f[N][2];
// f[i,s]表示以i为根节点的子树,根节点放( s == 1 )或者不放( s == 0 )的方案数;
int fa[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
f[u][0] = 1, f[u][1] = 1;
for (int i = h[u]; i != -1; i = ne[i])
{
int son = e[i];
dfs(son);
// 注意,放置方法是乘法;
f[u][1] *= (f[son][0] + f[son][1]);
f[u][0] *= f[son][1];
}
}
signed main(void)
{
while (cin >> n)
{
memset(h, -1, sizeof(h));
idx = 0;
memset(f, 0, sizeof(f));
memset(fa, 0, sizeof(fa));
int root = -1;
for (int i = 1; i <= n; i++)
{
int father, cnt;
scanf("%lld:(%lld)", &father, &cnt);
father++;
for (int i = 1; i <= cnt; i++)
{
int son;
cin >> son;
son++;
add(father, son);
fa[son] = father;
}
}
for (int i = 1; i <= n; i++)
{
if (!fa[i])
{
root = i;
}
}
dfs(root);
// 总的放置方法=根节点放的放置方法 + 根节点不放的放置方法;
cout << f[root][0] + f[root][1] << endl;
}
return 0;
}