烽火传递 | FFY's Blog

题意

在某两座城市之间有 n 个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确的传递，在任意相邻的 m 个烽火台中至少要有一个发出信号。现在需要计算总共最少需要花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确的传递。

• 单调队列优化

  #include<cstdio>
  #include<cstring>
  #include<algorithm>
  using namespace std;
  const int maxn=1e5+10,inf=1e9+7;
  int n,t,m,f[maxn][2],v[maxn];
  int q[maxn<<1],p[maxn<<1];
  int main()
  {
    freopen("flame.in","r",stdin);
    freopen("flame.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%d",&v[i]); 
        int t=0,h=1;
        for(int i=1;i<=n;i++)
        { 
            int a=0;
            if(i-p[h]>m)h++;
            if(i>m)a=v[i]+q[h];else a=v[i];
            while(t>=h&&q[t]>a)t--; 
            q[++t]=a;p[t]=i;
        }
        int ans=inf;
        if(n-p[h]>=m)h++;
        for(int i=max(h,t-m+1);i<=t;i++)
        ans=min(ans,q[i]);
        printf("%d\n",ans);
    }
    return 0;
  }
  

---

可以加一位n+1,直接作为ans,省去后面的ans统计

可以省去一些麻烦(比如3个小时)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+10,inf=1e9+7;
int n,t,m,f[maxn][2],v[maxn];
int q[maxn<<1],p[maxn<<1];
int main()
{
    freopen("flame.in","r",stdin);
    freopen("flame.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%d",&v[i]); 
        int t=0,h=1;
        for(int i=1;i<=n+1;i++)//n+1
        { 
            int a=0;
            if(i-p[h]>m)h++;
            if(i>m)a=v[i]+q[h];else a=v[i];
            while(t>=h&&q[t]>a)t--; 
            q[++t]=a;p[t]=i;
        }
        printf("%d\n",q[t]);//直接输出
    }
    return 0;
}