线段树和单调队列优化DP---POJ2373解题报告 - c++编程基础

n,l,inf,dp[L],queue[L],head,tail,size;

void insert(int idx)
{
tail++;
while(headdp[idx]) tail--;
queue[tail]=idx;
while(idx-queue[head]>=size) head++;
}

int dpro(void)
{
if(b<1) return -1;
dp[0]=0;
size=2*b+1;
head=0;
tail=-1;

for(int i=a; i<=b; i++) if(dp[2*i]<=inf) dp[2*i]=1;
int seg = 2*b-2*a;
for(int i=0; i<=seg; i+=2) insert(i);

for(int i=2*b; i<=l; i+=2)
{
if(i-a*2>seg) insert(i-a*2);
while(i-queue[head]>=size) head++;
if (dp[i]<=inf) dp[i]=dp[queue[head]]+1;

}

if(dp[l]>=inf) return -1;
else return dp[l];
}

int main()
{
while (scanf("%d%d", &n, &l)!=EOF) {

scanf("%d%d", &a, &b);
inf = (l/a)+9;
for(int i=0; i<=l; i++) dp[i]=inf;

for(int i=0; i int s, e;
scanf("%d%d", &s, &e);
for(int j=s+1; j }

if(l&1==1) printf("-1\n");
else printf("%d\n", dpro());
}
return 0;
}

作者：sunny606

线段树和单调队列优化DP---POJ2373解题报告(二)