题号：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]; } |