該題和紫書上的一道題很相似,都是用滑動窗口來優化DP。 ?紫書上題目見這里:[點擊打開鏈接](http://blog.csdn.net/weizhuwyzc000/article/details/47321975)? ? ? 該題鏈接:[點擊打開鏈接](http://acm.uestc.edu.cn/#/problem/show/1132)
該題也是需要利用滑動窗口優化的。 ? 首先我們很容易想到這樣的狀態表示:d[i][j]表示第i朵花展出時,醬神在位置j處時的最優解。 ?那么我們首先按照時間從小到大排序,這樣相臨兩個時間差乘以速度,就可以知道每次醬神能走的位置范圍,然后狀態轉移過去就行了d[i][j] = max(d[i-1][k]+ a[i].b - abs(j-a[i].a));。但是這樣的復雜度是O(n*n*m)需要優化DP。
對于每一個i和j來說,我們可以發現,其可以轉移到的范圍是j-k*d~j+k*d,對于每一個i,移動范圍相同。而j又是從小到大增加的,這不就是一個滑動窗口嗎? ?所以我們可以用滑動窗口優化第三重循環,在平攤意義下,查詢最小值的復雜度為O(n)。
細節參見代碼:
~~~
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const int maxn = 100000+5;
const int maxm = 100+5;
const double PI = acos(-1.0);
int T,l,r,id[maxn];
ll d[maxm][maxn]={0},v[maxn],dd,n,m;
struct node {
ll a, b, t;
bool operator < (const node& rhs) const {
return t < rhs.t;
}
}a[maxn];
int main() {
while(~scanf("%lld%lld%lld",&n,&m,&dd)) {
for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&a[i].a,&a[i].b,&a[i].t);
sort(a+1,a+1+m);
for(ll i=1;i<=m;i++) {
ll t = a[i].t - a[i-1].t;
l = 0; r = 0;
ll len = min(n,1+t*dd);
for(ll k=1;k<=len;k++) {
while(l < r && v[r-1] <= d[i-1][k]) r--; //刪除隊列中無用的元素
v[r] = d[i-1][k]; //加入新元素
id[r++] = k; //記錄單調隊列中元素對應的原位置
}
for(ll j=1;j<=n;j++) {
if(id[l] < j-t*dd) l++;
if(j+t*dd <= n) {
ll u = j+t*dd;
while(l < r && v[r-1] <= d[i-1][u]) r--;
v[r] = d[i-1][u];
id[r++] = u;
}
d[i][j] = v[l] + a[i].b - abs(j-a[i].a);
}
}
ll ans = -INF;
for(int i=1;i<=n;i++) ans = max(ans,d[m][i]);
printf("%lld\n",ans);
}
return 0;
}
~~~
- 前言
- 1608 - Non-boring sequences(折半遞歸。。暫且這么叫吧)
- 11491 - Erasing and Winning(貪心)
- 1619 - Feel Good(高效算法-利用數據結構優化-優先隊列)
- hdu-4127 Flood-it!(IDA*算法)
- UESTC 1132 醬神賞花 (用數據結構優化DP)
- HDU 2874 Connections between cities(LCA離線算法)
- Codeforces Round #317 A. Lengthening Sticks(組合+容斥)
- HDU 3085 Nightmare Ⅱ(雙向BFS)
- HDU 5592 ZYB&#39;s Premutation(二分+樹狀數組)
- Codeforces Round #320 (Div. 1) C. Weakness and Poorness(三分)
- HDU 5212 Code(容斥)
- HDU 5596 GTW likes gt(multiset)
- FZU 2159 WuYou(貪心)
- HDU 3450 Counting Sequences(DP + 樹狀數組)
- HDU 5493 Queue(二分+樹狀數組)
- HDU 1166 敵兵布陣(線段樹版)
- HDU 1394 Minimum Inversion Number(樹狀數組||線段樹)
- HDU 2795 Billboard(線段樹)
- POJ 2828 Buy Tickets(樹狀數組)
- 《完全版線段樹》- NotOnlySuccess
- POJ 2886 Who Gets the Most Candies?(樹狀數組+二分)
- HDU 1698 Just a Hook(線段樹區間修改)
- POJ 3468 A Simple Problem with Integers(線段樹|區間加減&amp;&amp;區間求和)
- POJ 2528 Mayor&#39;s posters(線段樹區間修改+離散化)
- HDU 5606 tree(并查集)
- POJ 3734 Blocks(矩陣優化+DP)
- POJ 3233 Matrix Power Series(矩陣優化)
- HDU 5607 graph(矩陣優化+概率DP)
- POJ 2777 Count Color(線段樹區間修改+位運算)
- POJ 1436 Horizontally Visible Segments(線段樹區間修改)
- UVA 1513 - Movie collection(樹狀數組)
- UVA 1232 - SKYLINE(線段樹區間更新)
- 11525 - Permutation(二分+樹狀數組)
- 11402 - Ahoy, Pirates!(線段樹區間更新(標記重疊的處理))
- Educational Codeforces Round 6 E. New Year Tree(DFS序+線段樹)