3768 monkey

设f[i][j]：第i只猴子跳到第j棵树的最小劳累值

可以得到

f [ i ][ j ] = min( f[ i ][ ii ] + (d[ j ]  >=  d[ ii ] ) )    //  ii  =  j  -  k[ i ]; ii  <  j;ii ++

再想一想，如果 f[ i ][ jj ]为最小值，那么就算h[i] > h[jj] ，f[ i ][ jj ] + 1 也一定是最小的（可能f[ i ][ jj ] 等于f[i][iii]，f[ i ][ jj ] + 1 > f[i][iii],但处理一下就可以了），所以先可以不考虑是否+1，所以可以用一个单调上升序列（s）。因为队头是最小的，所以f[i][j] = f[s[head]] + (h[j] >= h[s[head]]) 。再将f[i][j]进入队列，但这里需要特殊处理一下，如果f[i][j]==f[s[tail]] && h[j] > h[s[tail]]也可将s[tail]踢出序列

参考代码：
 

for(i = 1;i <= q;i++){
    memset(s,0,sizeof s);
    head = tail = 1;
    f[i][1] = 0;
    s[1] = 1;
    for(j = 2;j <= n;j++){
        while(s[head] < j - k[i] && head < tail)
            head++;
        f[i][j] = f[i][s[head]];
        if (h[j] >= h[s[head]])
            f[i][j]++;
        while((f[i][j]<f[i][s[tail]]||(f[i][j]==f[i][s[tail]]&&h[j]>h[s[tail]]))&&head<tail)
            tail--;
        s[++tail] = j;
    }
    printf(\"%d\\n\",f[i][n]);
}