昆明网站建设赵,wordpress主题机制,有哪些好的网站建设公司,怎么做旅游网站Acwing 1089. 烽火传递
题意#xff1a;
有n个数#xff0c;要保证每m个数中必须选一个#xff0c;问所选数的最小总和是多少
题解#xff1a;
我一开始设的状态为:dp[i]表示前i个数选完的最小值#xff0c;第i个数可以选也可以不选#xff0c;但是这样一个状态…Acwing 1089. 烽火传递
题意
有n个数要保证每m个数中必须选一个问所选数的最小总和是多少
题解
我一开始设的状态为:dp[i]表示前i个数选完的最小值第i个数可以选也可以不选但是这样一个状态如果要这么考虑的话应该开二维数组来表示状态且答案不好求所以我们改变状态定义
我们定dp[i]表示第i个必选的且前i-1个满足条件的最小值 我们可以得到状态方程为dp[i]min(dp[x])a[i],x∈[i-m,i-1] dp[x]通过单调队列可以得到
那最终的答案是什么想想我们的状态为dp[i]前i-1个满足条件,第i个一定选择那么也就是如果i∈[n-m1,n],所有的情况就都会考虑到即任意m个数都存在一个被选所以答案就是min(dp[n-m1],d[n-m2]…dp[n])在最后m个数中选一个的最小值情况
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn2e59;
int a[maxn];
int q[maxn];
int dp[maxn];
int main()
{int n,m;cinnm;for(int i1;in;i){cina[i];}int hh0,tt0;for(int i1;in;i){if(q[hh]mi)hh;dp[i]dp[q[hh]]a[i];while(hhttdp[q[tt]]dp[i])tt--;q[tt]i;} int res1e9;for(int in-m1;in;i)resmin(res,dp[i]); coutres;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]
*/
