我多放了一个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];
}