uva11285 uvalive3983 Hackers' Crackdown // AC // A.myc #include<iostream> #include<cmath> #include<stdio.h> #include<string.h> using namespace std; const int maxn=100005; struct dpnode{ int idx; int val; }; dpnode queue[maxn]; int head,tail; int dp[maxn]; int s[maxn]; int d[maxn]; int w[maxn]; int c,n; void Dp(){ head=tail=0; memset(dp,-1,sizeof(dp)); dp[0]=0; dp[1]=2*d[1]; queue[tail].idx=0; queue[tail++].val=dp[0]; queue[tail].idx=1; queue[tail++].val=dp[1]; // ## for(int i=2;i<=n;i++){ while((w[i]-w[queue[head].idx])>c) head++; // ## for(int j=head;queue[j].idx<i && j!=tail;j++){ if(w[i]-w[queue[j].idx]<=c && (dp[i]==-1 || (dp[queue[j].idx]+d[queue[j].idx+1]+s[i]-s[queue[j].idx+1]+d[i])<dp[i])){ dp[i]=(dp[queue[j].idx]+d[queue[j].idx+1]+s[i]-s[queue[j].idx+1]+d[i]); } } while(i<n && (dp[i]+d[i+1]-s[i+1])<(queue[tail-1].val+d[queue[tail-1].idx+1]-s[queue[tail-1].idx+1]) && tail>head) tail--; queue[tail].idx=i; queue[tail++].val=dp[i]; } } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d%d",&c,&n); int x0=0,y0=0; s[0]=0; w[0]=0; for(int i=1;i<=n;i++){ int x,y; scanf("%d%d%d",&x,&y,&w[i]); d[i]=x+y; s[i]=s[i-1]+abs((double)x-x0)+abs((double)y-y0); w[i]+=w[i-1]; x0=x,y0=y; } Dp(); printf("%d\n",dp[n]); if(T>0) printf("\n"); // ## } return 0; }
相关推荐
Hackers delight 2nd edition黑客必备
Linux Kernel Hackers' Guide Due to the fact that nearly every post to this site recently has been either by rude cracker- wannabes asking how to break into other people's systems or a request for ...
Addison Wesley - Hackers Delight__ 2002
Linux Basics for Hackers_ Getting Started
Now that storage and collection technologies are cheaper and more precise, methods for extracting ... Machine Learning for Hackers is ideal for programmers from private, public, and academic sectors.
car hackers handbook
The Web Application hackers book!!!!!!!!!
Machine Learning for Hackers 英文无水印pdf pdf所有页面使用FoxitReader和PDF-XChangeViewer测试都可以打开 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传者...
Bayesian methods for hackers.pdf
Linux Hackers-manual 2019 version. Advance your Linux skills
Hackers and Painters,黑客与画家,写的非常不错的一本书,这是英文版的。
Hackers
Linux Basics for Hackers 中文版
Bayesian Methods for Hackers 书的ipynb格式,可以直接用jupyter打开,书中的代码可直接按shift+enter执行
Linux Basics for Hackers: Getting Started with Networking, Scripting, and Security in Kali (AZW3)
英文版Hackers.and.Painters.May.2010(完美版).pdf