alan的DP题

NC219233. alan的DP题

描述

alan最近一共购入了 $n$ 件物品，其中第 $i$ 件物品的价值为 $i$ ，并且每个物品都有一些的用处，
第 $i$ 个物品存在最多一个 $p[i]$ 的依赖关系，那么就代表第 $i$ 号物品的用处恰好包含了第 $p[i]$ 件物品的用处
细心的小y帮alan把这些物品按用处排列好，发现这恰好形成了一个森林，第i个物品的父亲是 $p[i]$ 。
alan的同学前来购买物品，第 $i$ 个同学希望能买第 $c[i]$ 件物品，或者一件用处能代替 $c[i]$ 的物品
如果 $c[i]$ $=$ $0$ ，那么表示这个同学想任意购买一件物品。

alan觉得这很像是一个收益DP题，alan想知道自己最多获得多少的收益

注意：每个物品只有一件，也就是所有同学购买的物品应该互不相同，但是也有同学没有购买物品的情况这样是允许的，题目只是要求最大收益

输入描述

第一行两个数  , 
第二行n个数  ，注意  可能等于0
第三行m个数

输出描述

表示alan最多能获得的收益

示例1

输入:

4 3
3 1 0 1
2 0 1

输出:

说明:

1号物品包含了3号物品的作用

2号物品包含了1号物品的作用

4号物品包含了1号物品的作用

对于第1位同学可以买第2件，显然第2件是满足条件的

对于第2位同学，表示这个同学想任意购买一件物品，因此买第3件

第三位同学要买一个物品包含了1号物品的作用，1号 2号 4号都是满足条件的，其中2号已经买过了，1号和4号显然4号的价值更大，因此买第4件

综上所述收益为2+3+4=9

上次编辑到这里，代码来自缓存点击恢复默认模板

C(clang11) 解法, 执行用时: 763ms, 内存消耗: 59888K, 提交时间: 2021-04-19 09:07:40

#include <stdio.h>

#define N 3000005

int myset[N], xq[N];

void init() {
	for (int i = 1; i <= N; i++) {
		myset[i] = i;
	}
}

int find_set(int x) {
	return (xq[x] > 0|| !x) ? x : (myset[x] = find_set(myset[x]));
}

int main() {
	init();
	int n, m;
	scanf("%d %d", &n, &m);
	
	for (int i = 1; i <= n; i++) {
		scanf("%d", &myset[i]); // 表示第i号商品包含myset[i]号商品的作用 
	}
	
	for (int i = 1; i <= m; i++) {
		int b;
		scanf("%d", &b);
		++xq[b]; //表示b号商品需求+1 
	}
	
	long long ans = 0;
	for (int i = n; i >= 1; i--) {
		int t = find_set(i);
		if (xq[t]) {
			--xq[t];
			ans += i;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

C++(clang++11) 解法, 执行用时: 721ms, 内存消耗: 39380K, 提交时间: 2021-04-19 13:52:13

#include<bits/stdc++.h>
#define N 3000050
using namespace std;
int fa[N], p[N], size[N], n, m;
int get(int x) {
	return (fa[x] == x)? x : (fa[x] = get(fa[x]));
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++) scanf("%d", &p[i]), fa[i] = p[i];
	for(int i = 1, x = 0; i <= m; i ++) scanf("%d", &x), size[x] ++, fa[x] = x; 
	
	long long ans = 0;
	for(int i = n; i >= 1; i --) {
		int x = get(i);
		if(size[x]) {
			ans += i; size[x] --;
			if(!size[x]) fa[x] = p[x];
		}
	} printf("%lld", ans);
	return 0;
}