COCI ACM —— 线段树+枚举

本文主要是介绍COCI ACM —— 线段树+枚举，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

现在哟n道题目，有三个人对这些题目打分(1~5)，现在要将这n道题目划分为3个连续的区间，分配给这三个人去做，每个人的值就是他对于他负责的区间的打分的值的和。问你所有人的值的和最小是多少。

题解：

那么其实这道题的解法很明显，首先每个人有先后顺序，但是只有3个人，所以可以暴力枚举每个人的先后情况。
然后对于当前的情况，我们可以枚举第一个人负责的区间到哪，然后找到后面区间的最优分配方法，那么设后面的每个位置的值是$bi-ci$，然后维护一个前缀和，找到其中的最小值就是第二个人到这是最优的。
然后一开始写的线段树退化了，需要用线段树优化一样去每个位置都维护最小值的位置和值。然后好像要用快读。
然后好像有6n的方法可以去做，但是我懒得想。

#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
namespace Fast_IO { //orz laofuconst int MAXL((1 << 18) + 1); int iof, iotp;char ioif[MAXL], * ioiS, * ioiT, ioof[MAXL], * iooS = ioof, * iooT = ioof + MAXL - 1, ioc, iost[55];char Getchar() {if (ioiS == ioiT) {ioiS = ioif; ioiT = ioiS + fread(ioif, 1, MAXL, stdin); return (ioiS == ioiT ? EOF : *ioiS++);}else return (*ioiS++);}void Write() { fwrite(ioof, 1, iooS - ioof, stdout); iooS = ioof; }void Putchar(char x) { *iooS++ = x; if (iooS == iooT)Write(); }inline int read() {int x = 0; for (iof = 1, ioc = Getchar(); ioc<'0' || ioc>'9';)iof = ioc == '-' ? -1 : 1, ioc = Getchar();for (x = 0; ioc <= '9' && ioc >= '0'; ioc = Getchar())x = (x << 3) + (x << 1) + (ioc ^ 48); return x * iof;}inline long long read_ll() {long long x = 0; for (iof = 1, ioc = Getchar(); ioc<'0' || ioc>'9';)iof = ioc == '-' ? -1 : 1, ioc = Getchar();for (x = 0; ioc <= '9' && ioc >= '0'; ioc = Getchar())x = (x << 3) + (x << 1) + (ioc ^ 48); return x * iof;}template <class Int>void Print(Int x, char ch = '\0') {if (!x)Putchar('0'); if (x < 0)Putchar('-'), x = -x; while (x)iost[++iotp] = x % 10 + '0', x /= 10;while (iotp)Putchar(iost[iotp--]); if (ch)Putchar(ch);}void Getstr(char* s, int& l) {for (ioc = Getchar(); ioc <'a' || ioc>'z';)ioc = Getchar();for (l = 0; ioc <= 'z' && ioc >= 'a'; ioc = Getchar())s[l++] = ioc; s[l] = 0;}void Putstr(const char* s) { for (int i = 0, n = strlen(s); i < n; ++i)Putchar(s[i]); }
} // namespace Fast_IO
using namespace Fast_IO;
const int N=15e4+5;
pa mi[N*4];
int f[N*4],a[5][N],sum[5][N],p[5];
void push_down(int root){if(!f[root])return ;mi[root<<1].second+=f[root];mi[root<<1|1].second+=f[root];f[root<<1]+=f[root];f[root<<1|1]+=f[root];f[root]=0;
}
void build(int l,int r,int root,int p,int v){if(l==r){mi[root]={l,v};return ;}int mid=l+r>>1;if(mid>=p)build(l,mid,root<<1,p,v);elsebuild(mid+1,r,root<<1|1,p,v);if(mi[root<<1].second<mi[root<<1|1].second)mi[root]=mi[root<<1];elsemi[root]=mi[root<<1|1];
}
pa query(int l,int r,int root,int ql,int qr){if(l>=ql&&r<=qr)return mi[root];push_down(root);int mid=l+r>>1;pa ans={0,1e9};if(mid>=ql)ans=query(l,mid,root<<1,ql,qr);if(mid<qr){pa ne=query(mid+1,r,root<<1|1,ql,qr);if(ne.second<ans.second)ans=ne;}return ans;
}
int main()
{int n;n=read();for(int i=1;i<=3;i++)for(int j=1;j<=n;j++)a[i][j]=read(),sum[i][j]=sum[i][j-1]+a[i][j];for(int i=1;i<=3;i++)p[i]=i;int ans=1e9;do{//for(int i=1;i<N*4;i++)//mi[i]=1e9;memset(f,0,sizeof(f));int s=0;for(int i=1;i<=n;i++){build(1,n,1,i,s+a[p[2]][i]-a[p[3]][i]);s+=a[p[2]][i]-a[p[3]][i];}s=0;for(int i=1;i<=n-2;i++){s+=a[p[1]][i];//update(1,n,1,i,n,a[p[3]][i]-a[p[2]][i]);pa mm=query(1,n,1,i+1,n-1);ans=min(ans,s+sum[p[2]][mm.first]-sum[p[2]][i]+sum[p[3]][n]-sum[p[3]][mm.first]);}}while(next_permutation(p+1,p+1+3));printf("%d\n",ans);return 0;
}

这篇关于COCI ACM —— 线段树+枚举的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---