该题和紫书上的一道题很相似，都是用滑动窗口来优化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; } ~~~