好像没有排序也能过
查看原帖
好像没有排序也能过
966994
hellomoon楼主2024/6/8 14:35

我多放了一个visited标记是否能跳跃到某一时间点,然后就能过,不标记就过不了,大概是因为条件:如果他正空闲时有一任务他必须开始执行任务,不标记的话,就可能忽略前面的任务,直接从当前任务开始,即使把前面的休息时间全算为0,最后答案也可能大于正确答案 我的代码:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct inf
{
	int e;
	int next;
};
vector<inf>e[10005];
bool visited[10005];
int dp[10005];
int main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= k; i++)
	{
		int p, t;
		cin >> p >> t;
		e[p].push_back({ p + t - 1,0 });
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < e[i].size(); j++)
		{
			int z = e[i][j].e + 1;
			while (z<=n&&!e[z].size())
				z++;
			e[i][j].next = z;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (!e[i].size())
			dp[i] = i;
		else
			break;
		visited[i] = 1;
	}
	visited[0] = 1;
  	for (int i = 1; i <= n; i++)
	{
		if (!visited[i - 1])
			continue;
		for (int j = 0; j < e[i].size(); j++)
		{
			dp[e[i][j].next-1] = max(dp[e[i][j].next-1], dp[i-1] + e[i][j].next - e[i][j].e - 1);
			visited[e[i][j].next - 1] = 1;
		}
	}
	cout << dp[n];
}
2024/6/8 14:35
加载中...