[BZOJ 2442]修剪草坪
转载请注明出处:http://danihao123.is-programmer.com/
单调队列优化DP……
bi了doge了……现在才能学会一些简单的单调队列优化DP
代码:
/************************************************************** Problem: 2442 User: danihao123 Language: C++ Result: Accepted Time:104 ms Memory:2532 kb ****************************************************************/ #include <cstdio> #include <algorithm> #include <queue> #include <deque> using namespace std; const int maxn=100001; struct DQueue{ queue<long long> A; deque<long long> d; void push(long long x){ A.push(x); while((!d.empty()) && (d.back()<x)) d.pop_back(); d.push_back(x); } long long top(){ return d.front(); } long long pop(){ if(d.front()==A.front()) d.pop_front(); A.pop(); } int size(){ return A.size(); } }; long long S[maxn],d[maxn]; DQueue Q; int main(){ register int i; int n,k; long long temp; scanf("%d%d",&n,&k); S[0]=0; for(i=1;i<=n;i++){ scanf("%lld",&temp); S[i]=S[i-1]+temp; } d[0]=0; Q.push(0); for(i=1;i<=n;i++){ if(Q.size()>k) Q.pop(); Q.push(d[i-1]-S[i]); d[i]=Q.top()+S[i]; d[i]=max(d[i],d[i-1]); } printf("%lld\n",d[n]); return 0; }
Feb 29, 2016 09:53:35 PM
%%%%%!!
这题窝当时 WA 了一上午 ……
Mar 02, 2016 12:37:47 PM
@Menci: %%%%%%我这提做了很长时间才会,而且没有您的题解我现在不会会单调队列优化DP的
Mar 03, 2016 11:22:11 AM
@danihao123: 说得好像我会一样
Mar 03, 2016 11:22:51 AM
@danihao123: 说得好像我会一样(手动滑稽