【Codeforces Round #515 (Div. 3) B. Heaters】dp

B. Heaters

题意

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

做法

dp[i]表示最后一个暖气放在i能使前i个格子都温暖的最小暖气数
$转移就很明显，dp[i]=mindp[j]+1(i?2?r+1<=j<i)$
这个dp明显可以用单调队列优化一下，做法就变成O(n)的啦！

代码

//O(n^2)
#include<stdio.h>
#include<iostream>
using namespace std;
const int maxn = 1e3+5;
const int INF = 0x3f3f3f3f;
int dp[maxn];
int a[maxn];
int main()
{
    int n,r;scanf("%d%d",&n,&r);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=0;i<=n;i++) dp[i]=INF;int pos=0;for(int i=1;i<=min(n,r);i++){
    if(a[i]==1){
    dp[i]=1;pos=i;}}for(int i=pos+1;i<=n;i++){
    if(a[i]==0) continue;for(int j=max(1,i-2*r+1);j<i;j++)  dp[i]=min(dp[i],dp[j]+1);}int ans=INF;for(int i=max(1,n-r+1);i<=n;i++) ans=min(ans,dp[i]);if(ans==INF) printf("-1\n");else printf("%d\n",ans);return 0;
}
//单调队列优化O(n)
#include<stdio.h>
#include<iostream>
using namespace std;
typedef pair <int, int> pii;
const int maxn = 1e3+5;
const int Mod=1000000007;
const int INF = 0x3f3f3f3f;
int dp[maxn];
int a[maxn];
pii que[maxn<<2];
int main()
{
    int n,r;scanf("%d%d",&n,&r);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=0;i<=n;i++) dp[i]=INF;int pos=0;for(int i=1;i<=min(n,r);i++){
    if(a[i]==1){
    dp[i]=1;pos=i;}}int tail=-1,head=0;if(pos!=0) que[++tail]=pii(pos,2);for(int i=pos+1;i<=n;i++){
    if(a[i]==0) continue;while(tail>=head&&i-que[head].first>2*r-1) head++;if(tail>=head) dp[i]=que[head].second;else continue;while(tail>=head&&que[head].second>=dp[i]+1) head++;while(tail>=head&&que[tail].second>=dp[i]+1) tail--;que[++tail]=pii(i,dp[i]+1);}int ans=INF;for(int i=max(1,n-r+1);i<=n;i++) ans=min(ans,dp[i]);if(ans==INF) printf("-1\n");else printf("%d\n",ans);return 0;
}