nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

cf515B

链接

http://codeforces.com/contest/1066/problem/B

题意

        有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值单调减的单调队列即可。