发布于2018年7月26日2018年8月24日 由itewqq[训练指南][单调队列][DP] 滑动窗口单调队列优化线性dp 输出格式坑 LA3983 我上次wa两个小时是什么时候？？？妈的这个题格式。。。提示一个PE能死啊我去 直接暴力dp很好想但是复杂度爆炸，经过转换后可以把i和j分离开，然后j的那一部分就成了独立的只跟j有关的，这时候就可以把他当成一个新的量，然后求的时候就是在weight(j+1,i)<c的条件下（可以发现这其实是一个滑动的窗口）求出使得wav最小的j，就很像基本的dp了，只不过求最小j的时候用单调队列优化了。 #include #include #include #include #include #include #include #include #include //#include #include #include using namespace std; typedef long long LL; const int maxn=1e5+5; const int MOD=1e9+7; struct wp { int x,y,w; }wps[maxn]; int dor[maxn],df[maxn],hd[maxn],d[maxn],tw[maxn]; int pst[maxn],f,r;//f==r means empty void del(int x) { if(x==pst[f]) f++; } void ins(int x) { r=upper_bound(pst+f,pst+r,x)-pst;//upper pst[r++]=x; } int main() { //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); int T,c,n,temp,left; scanf("%d",&T); while(T--) { memset(wps,0,sizeof(wps)); f=r=0; scanf("%d%d",&c,&n); scanf("%d%d%d",&wps[1].x,&wps[1].y,&wps[1].w); dor[1]=wps[1].x+wps[1].y; tw[1]=wps[1].w; for (int i=2;i<=n;i++) { scanf("%d%d%d",&wps[i].x,&wps[i].y,&wps[i].w); tw[i]=tw[i-1]+wps[i].w; dor[i]=abs(wps[i].x)+abs(wps[i].y); df[i]=df[i-1]+abs(wps[i].x-wps[i-1].x)+abs(wps[i].y-wps[i-1].y); } left=0; ins(d[0]+dor[1]-df[1]); for (int i=1;i<=n;i++) { while(tw[i]-tw[left]>c)//error? { del(d[left]+dor[left+1]-df[left+1]); left++; } d[i]=pst[f]+dor[i]+df[i]; ins(d[i]+dor[i+1]-df[i+1]); } printf("%d\n",d[n]); if(T) printf("\n"); } return 0; }
