找施工员在哪个网站上找,wordpress好用主题,各种网站,自己电脑wordpress题意#xff1a; 给定一段长为N的序列#xff0c;选取其中的至多M段使这些子段和最大。 当N1000时#xff0c;我们可以采用动态规划解法 令\(dp[i][j][k]\)代表当前选至位置\(i\)处于第\(j\)段当前是否选取(1选0不选) 则转移为\(dp[i][j][0]max(dp[i-1][j][1],dp[i-1][j][0]…题意 给定一段长为N的序列选取其中的至多M段使这些子段和最大。 当N1000时我们可以采用动态规划解法 令\(dp[i][j][k]\)代表当前选至位置\(i\)处于第\(j\)段当前是否选取(1选0不选) 则转移为\(dp[i][j][0]max(dp[i-1][j][1],dp[i-1][j][0])\)\(dp[i][j][1]max(dp[i-1][j-1][0],dp[i-1][j][1])score[i]\) 其中\(i\)的一维可以滚动掉 Code #include cstdio
#include cstring
int max(int x,int y){return xy?x:y;}
const int N503;
const int inf0x3f3f3f3f;
int dp[N][N][2],n,k,score[N];
void init()
{scanf(%d%d,n,k);for(int i1;in;i)scanf(%d,scorei);memset(dp,-0x3f,sizeof(dp));dp[1][0][0]0,dp[1][1][1]score[1];
}
void work()
{for(int i2;in;i)for(int j0;jk;j){dp[i][j][0]max(dp[i-1][j][1],dp[i-1][j][0]);dp[i][j][1]max(dp[i-1][j-1][0],dp[i-1][j][1])score[i];}int ans-inf;for(int i0;ik;i)ansmax(ans,max(dp[n][i][0],dp[n][i][1]));printf(%d\n,ans);
}
int main()
{init();work();return 0;
}当N100,000时我们可以采用贪心解法 注意到每次选取时一段连续的正数或者连续的负数要么我们不取选它要么全部选走。 我们先缩个点使序列变成正负数交错的其中第一项和最后一项的负数我们一定不去选择故舍去。 设当前有\(k\)个正数。 则当\(Mk\)时直接选取\(k\)个正数即可。 当\(Mk\)时对每个正数我们有两种选择放弃它或者跨过负数选择它。 则当选中一个负数\(a\)时我们损失了\(-a\)当放弃一个正数\(b\)时我们损失了\(b\) 则不管哪种情况我们只需要找到绝对值最小的一个数选择它或者放弃它 采用二叉堆维护这个最小值 当这个最小值被操作时其实等价于新产生了一个权值为 它和它旁边的两个元素的权值和 的新元素这时候产生的新数列一定会少一个正数 值得一提的是当第一项和最后一项是负数的时候不一定一定减少一个正数所以我们根据贪心不去选择这些点即可 合并元素可以采用链表进行维护 Code:实在是不好看QAQ #include cstdio
#include cstring
#include iostream
#include queue
#define ll long long
#define P pair ll,ll
using namespace std;
const int N1000010;
ll a[N],b[N],n0,k,n,pre[N],suc[N],cnt,used[N];
ll labs(ll x){return x0?x:-x;}
void init()
{scanf(%lld%lld,n0,k);for(int i1;in0;i)scanf(%lld,ai);int k0;a[0]-1;while(a[k]0) k;for(int ik;in0;i){if(a[i]*a[i-1]0)b[n]a[i];elseb[n]a[i];}while(nb[n]0) n--;for(int i1;in;i){pre[i]i-1;suc[i]i1;}suc[0]1;suc[n]0;
}
priority_queue P,vector P ,greater P q;
P p;
void work()
{for(int i1;in;i){if(b[i]0) cnt;p.firstlabs(b[i]);p.secondi;q.push(p);}while(cntk){int posq.top().second;q.pop();if(used[pos]) continue;if(!suc[pos]b[pos]0){suc[pre[pos]]suc[pos];pre[suc[pos]]pre[pos];continue;}if(!pre[pos]b[pos]0){pre[suc[pos]]pre[pos];suc[pre[pos]]suc[pos];continue;}used[pre[pos]]used[suc[pos]]1;b[pos]b[pre[pos]]b[suc[pos]];cnt--;if(pre[pos]){pre[pos]pre[pre[pos]];suc[pre[pos]]pos;}if(suc[pos]){suc[pos]suc[suc[pos]];pre[suc[pos]]pos;}p.firstlabs(b[pos]),p.secondpos;q.push(p);}int nowsuc[0];ll ans0;while(now){if(b[now]0) ansb[now];nowsuc[now];}printf(%lld\n,ans);
}
int main()
{init();work();return 0;
} 当N1,000,000时我们可以将算法近似优化到\(O(N)\) 具体大家可以参考出题人的题解 我在这里解释一下这个近似原题解没有说道找到第\(k\)值的问题 主要就是利用基于快速排序思想的STL函数\(nth\_element\)可以在近似\(O(n)\)的复杂度找到第\(k\)值 关于第k值 代码我没写感觉不太好写 转载于:https://www.cnblogs.com/butterflydew/p/9280322.html
