wordpress的知名网站,企业网站开发制作,沈阳做网站找黑酷科技,深圳恒诚信企业管理有限公司正题
题目链接:https://www.luogu.com.cn/problem/P4852 题目大意
给出n,m,c,dn,m,c,dn,m,c,d#xff0c;有n∗cmn*cmn∗cm张卡牌。进行nnn次连抽mmm次单抽#xff0c;连抽连续ccc张卡牌会获得第一张卡牌的欧气值#xff0c;单抽可以获得抽到卡牌的欧气值。不能连续进行dd…正题
题目链接:https://www.luogu.com.cn/problem/P4852 题目大意
给出n,m,c,dn,m,c,dn,m,c,d有n∗cmn*cmn∗cm张卡牌。进行nnn次连抽mmm次单抽连抽连续ccc张卡牌会获得第一张卡牌的欧气值单抽可以获得抽到卡牌的欧气值。不能连续进行ddd次单抽求最大欧气值之和。 解题思路
定义fi,jf_{i,j}fi,j表示进行iii次连抽之后抽到了第jjj张卡牌的最大欧气值。
因为一定是先进行若干次单抽可以为0再进行一次连抽。所以我们先用单调队列转移单抽也就是fi,jmax{fi−1,ksum(k1,j)}(j−d≤k≤j)f_{i,j}max\{f_{i-1,k}sum(k1,j)\}(j-d\leq k\leq j)fi,jmax{fi−1,ksum(k1,j)}(j−d≤k≤j) 然后转移连抽fi,jfi,j−caj−c1f_{i,j}f_{i,j-c}a_{j-c1}fi,jfi,j−caj−c1注意因为不能连续多抽所以要倒着转移
然后转移的时候记录方案就好了时间复杂度O(mcn2)O(mcn^2)O(mcn2) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N2e510;
int n,m,c,d,a[N];
int f[45][N],g[45][N];
dequeint q;
void Write(int dep,int x){if(!dep)return;Write(dep-1,g[dep][x]);printf(%d ,x-c1);
}
int main()
{scanf(%d%d%d%d,n,m,c,d);for(int i1;ic*nm;i){scanf(%d,a[i]);a[i]a[i-1];}memset(f,0xcf,sizeof(f));f[0][0]0;for(int i1;in1;i){while(!q.empty())q.pop_back();for(int j(i-1)*c;jc*nm;j){while(!q.empty()f[i-1][q.back()]-a[q.back()]f[i-1][j]-a[j])q.pop_back();q.push_back(j);while(!q.empty()q.front()j-d)q.pop_front();f[i][j]f[i-1][q.front()]a[j]-a[q.front()];g[i][j]q.front();}if(i!n1){for(int jc*nm;jc;j--){f[i][j]f[i][j-c]a[j-c1]-a[j-c];g[i][j]g[i][j-c];}for(int j0;jc;j)f[i][j]-2147483647/3;}}printf(%d\n,f[n1][c*nm]);Write(n,g[n1][c*nm]);
}
