UESTC 1132 酱神赏花 （用数据结构优化DP）
最后更新于：2022-04-01 15:52:37
该题和紫书上的一道题很相似，都是用滑动窗口来优化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;
}
~~~