Scheduling to minimize the truncated gaps
The problem is polynomial-time solvable.
To avoid edge cases it is better to think that the job needs to be scheduled at time $0$ and that $c(0)=0$. 

Let $OPT[t,p]$ be the minimum amount of budget that needs to be spent in order to schedule the job in the first $t$ slots with an overall penalty of at most $p$ and with the additional constraint that the job must be scheduled at time $t$.

Let $P(t', t) = \Big\lfloor \frac{t-t'-1}{2} \Big\rfloor$ be the penalty incurred if the job is scheduled at times $t'$ and $t &gt; t'$ and is not scheduled at any time in-between.

Then $OPT[0,p] = 0$ and, for $t&gt;0$:
$$
OPT[t,p] = c(t) + \min_{\substack{t'=0,\dots,t-1 \\ P(t',t) \le p}} OPT\left[t', p - P(t',t) \right] 
$$

The minimum attainable penalty up to time $t$, with the constraint that the job is scheduled at time $t$, is then:
$$
\mu(t) = \min \{p \in \{1,\dots,\lfloor t/2 \rfloor\} \mid  OPT[t,p] \le B \}
$$

And the minimum attainable penalty for your problem is:
$$
\min_{t=0,\dots,n}  \left\{ \mu(t) + P(t,n+1) \right\}.
$$

Notice that there are at most $n \cdot (P(0,n)+1) = O(n^2)$ values $OPT[p,t]$ to compute.