Acwing 1089. 烽火傳遞

題意：

有n個數(shù)，要保證每m個數(shù)中必須選一個，問所選數(shù)的最小總和是多少

題解：

我一開始設的狀態(tài)為:dp[i]表示前i個數(shù)選完的最小值，第i個數(shù)可以選也可以不選，但是這樣一個狀態(tài)，如果要這么考慮的話應該開二維數(shù)組來表示狀態(tài)，且答案不好求，所以我們改變狀態(tài)定義：

我們定dp[i]表示第i個必選的，且前i-1個滿足條件的最小值
我們可以得到狀態(tài)方程為：dp[i]=min(dp[x])+a[i],x∈[i-m,i-1]
dp[x]通過單調隊列可以得到

那最終的答案是什么？想想我們的狀態(tài)為dp[i]，前i-1個滿足條件,第i個一定選擇，那么也就是如果i∈[n-m+1,n],所有的情況就都會考慮到（即任意m個數(shù)都存在一個被選），所以答案就是min(dp[n-m+1],d[n-m+2]…dp[n])，在最后m個數(shù)中選一個的最小值情況

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=2e5+9; int a[maxn]; int q[maxn]; int dp[maxn]; int main() {int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}int hh=0,tt=0;for(int i=1;i<=n;i++){if(q[hh]+m<i)hh++;dp[i]=dp[q[hh]]+a[i];while(hh<=tt&&dp[q[tt]]>=dp[i])tt--;q[++tt]=i;} int res=1e9;for(int i=n-m+1;i<=n;i++)res=min(res,dp[i]); cout<<res;return 0; } /* dp[i]選擇完前i個烽火臺的最低花費 第i個可以選，也可以不選 dp[i]=dp[i-1] 如果選： 選擇長度為j dp[i]=min(dp[i-j])+a[i] j:1~m x:i-m ~ i-1 dp[i]=min(dp[x])+a[i] */

總結

以上是生活随笔為你收集整理的Acwing 1089. 烽火传递的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。