nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog

cf515B

链接

题意

        有n个格子,每个格子有01权值,1代表这个格子可以安装暖气,每个暖气可以温暖距离自己小于r的格子,问最少安装几个暖气能温暖n个格子。
        1<=n<=1e3

题解

        dp[i]代表在第i个位置放一个暖气,能温暖前i个格子的最少安装的暖气数,
        dp[i] <--- dp[j] (i-j<r)
        答案在dp[n-r+1,n]上
        明显dp可以用单调队列优化,维护一个i单调增,dp值单调减的单调队列即可。