题解 P1280 【尼克的任务】
officeyutong
2017-09-28 22:19:32
#蒟蒻的题解
其实也就是一个分组背包而已..以任务开始的时间分组，所有开始时间相同的任务在同一组内
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <map>
using namespace std;
using int_t = unsigned long long int;
int main() {
int_t timeLimit, count;
cin >> timeLimit>>count;
//数据存在map里 map[任务开始时间]
map<int_t, vector < int_t>> tasks;
for (int i = 1; i <= count; i++) {
int_t start, cost;
cin >> start>>cost;
tasks[start].push_back(cost);
}
int_t dp[10001] = {0};
//开始dp
for (int_t time = timeLimit; time >= 1; time--) {
//如果当前时间点没有任务开始，则直接改为上一点的值+1
if (tasks.find(time) == tasks.end()) {
dp[time] = dp[time + 1] + 1;
continue;
}
vector<int_t> &vec = tasks[time];
//选择任务之前先对任务的结束时间从大到小排序
sort(vec.begin(), vec.end());
for (auto ptr = vec.begin(); ptr < vec.end(); ptr++) {
dp[time] = max(dp[time], dp[time + *ptr]);
}
}
cout << dp[1];
}
```