T3 暑假打工

solution

贪心题

注意到每天只能完成一项任务，并且任务报酬的时间 $<= m$ 。考虑倒序枚举每一天，选择本天中报酬最多并且任务报酬的时间 $<= m$的任务，

实现：

1. 将任务按报酬时间排序
2. 枚举每一天，用优先队列存储能有报酬的任务
3. 弹出队顶，累加 $ans$

时间复杂度：$O((n + m)logn)$

code

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

struct node{
	int a , b;
}p[N];

int n , m , idx = 1 , ans;
priority_queue<int> q;

bool cmp(const node &lhs , const node &rhs){
	return lhs.a < rhs.a;
}

int main(){
	cin >> n >> m;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> p[i].a >> p[i].b;
	}
	sort(p + 1 , p + n + 1 , cmp);
	
	for(int i = m - 1 ; i >= 0 ; i --){
		while(p[idx].a + i <= m && idx <= n){
			q.push(p[idx].b);
			idx ++;
		}
		if(!q.empty()){
			ans += q.top();
			q.pop();
		}
	}
	cout << ans;
	return 0;
}

T6 黄金商人

solution

由题可以得知题目中所给得是一个有向无环图（DAG)，所以我们可以按照拓扑序来遍历整个图

设 $dp_i$ 为 $i$ （不包括 $i$）按拓扑序到起始节点所有节点的最小权值，有:

随后在 DAG 上 dp , 更新 $ans$ 即可

时间复杂度：$O(n + m)$

code

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
const int inf = 0x3f3f3f3f;

int n , m , a[N] , dp[N] , d[N];
vector<int> g[N];
queue<int> q;

int main(){
	cin >> n >> m;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	for(int i = 1 ; i <= m ; i ++){
		int x , y;
		cin >> x >> y;
		g[x].push_back(y);
		d[y] ++;
	}
	for(int i = 1 ; i <= n ; i ++){
		if(d[i] == 0) q.push(i);
		dp[i] = INT_MAX;
	}
	int ans = INT_MIN;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		ans = max(ans , a[u] - dp[u]);
		
		for(auto v : g[u]){
			dp[v] = min(dp[v] , min(dp[u] , a[u]));
			if(-- d[v] == 0) q.push(v);
		}
	}
	cout << ans;
	return 0;
}