日度归档：25 7 月, 2017

洛谷 尼克的任务

发表评论

题号：P1280
参考：http://blog.csdn.net/zhhx2001/article/details/52213855
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1280
作者: Radium_ 更新时间: 2016-08-25 12:58

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,k;
struct s{
int start;
int duration;
bool operator < (s & o1){
    return start<o1.start;
}
}info[10005];
int f[10005];
int taskptr;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=k;i++)cin>>info[i].start>>info[i].duration;
    sort(info+1,info+k+1);
    taskptr=k;
    for(int i=n;i>=1;i--){
        if(info[taskptr].start!=i)
            f[i]=f[i+1]+1;
        else
            while(info[taskptr].start==i){
                f[i]=max(f[i],f[i+info[taskptr].duration]);
                taskptr--;
            }
    }
    cout<<f[1];
}

20180802更新：
查看的题解：https://www.luogu.org/blog/user3573/solution-p1280

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n, k;
struct task {
    int p, t;
    bool operator < (const task& t2) const {
        return p > t2.p;
    }
}ts[10005];
int f[10005];
int main(){
    cin >> n >> k;
    for (int i = 1; i <= k; i++)cin >> ts[i].p >> ts[i].t;
    sort(ts + 1, ts + k + 1);
    int tsptr = 1;
    for (int i = n; i > 0; i--) {
        if (ts[tsptr].p != i) {
            f[i] = f[i + 1] + 1;
            continue;
        }
        while (ts[tsptr].p == i) {
            f[i] = max(f[i], f[i + ts[tsptr].t]);
            tsptr++;
        }
    }
    cout << f[1];
}