題目鏈接:http://codeforces.com/contest/721/problem/E

----------------------------------------------------------------------------------

比賽的時候只想了一個初步的貪心思路后就直接用優(yōu)先隊列$+DP$亂搞了

這樣做的話冗余的狀態(tài)數(shù)是非常多的 最后果然$FST(TLE)$了

----------------------------------------------------------------------------------

比賽后一直在糾結(jié)有沒有什么貪心的思路可以減少狀態(tài)數(shù)的

然后發(fā)現(xiàn)其實我們只需要記錄

對于每一段光照區(qū)間 利用完這個區(qū)間后的最多唱歌次數(shù) 如果有多個滿足的再記錄最左的位置

這樣狀態(tài)數(shù)就只有$O(n)$的級別了

再來考慮轉(zhuǎn)移的時候是否具有單調(diào)性 稍稍想想就能發(fā)現(xiàn)這一部分直接寫一個單調(diào)隊列就好

最后總的復(fù)雜度是$O(n)$的

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5 + 10; 4 int qdist[N], qans[N]; 5 int l, n, p, t; 6 void update(int x, int y, int &tdist, int &tans, int d, int a) 7 { 8 int cnt = (y - max(x, d + t)) / p; 9 a += cnt; 10 d = max(x, d + t) + cnt * p; 11 if(a > tans || (a == tans && d < tdist)) 12 { 13 tans = a; 14 tdist = d; 15 } 16 } 17 int main() 18 { 19 scanf("%d%d%d%d", &l, &n, &p, &t); 20 int front = 0, tail = 0, ans = 0; 21 qdist[tail] = -t; 22 qans[tail] = 0; 23 ++tail; 24 int x, y, tdist, tans; 25 while(n--) 26 { 27 scanf("%d%d", &x, &y); 28 tdist = y; 29 tans = 0; 30 front = max(front - 1, 0); 31 while(front < tail) 32 { 33 if(qdist[front] + t + p > y) 34 break; 35 update(x, y, tdist, tans, qdist[front], qans[front]); 36 ++front; 37 } 38 if(ans < tans) 39 { 40 ans = tans; 41 qdist[tail] = tdist; 42 qans[tail] = tans; 43 ++tail; 44 } 45 } 46 printf("%d\n", ans); 47 return 0; 48 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/sagitta/p/5925785.html

總結(jié)

以上是生活随笔為你收集整理的codeforces 721E Road to Home的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。