亳州建设局网站,wordpress内置播放器,苏州网上挂号,宁波网站建设运营Description 给定一个长度为 \(n\) 的数列 \(a\) #xff0c;你可以任意选择一个区间 \([l,r]\) #xff0c;并给区间每个数加上一个整数 \(k\) #xff0c;求这样一次操作之后数列中最多有多少个数等于 \(c\)。 \(n,c,a_i\leq 10^5\) Solution 假设当前选择区间的右端点为 …Description 给定一个长度为 \(n\) 的数列 \(a\) 你可以任意选择一个区间 \([l,r]\) 并给区间每个数加上一个整数 \(k\) 求这样一次操作之后数列中最多有多少个数等于 \(c\)。 \(n,c,a_i\leq 10^5\) Solution 假设当前选择区间的右端点为 \(r\)那我们要强制将 \(a_r\) 这个元素变为 \(c\)不然可以通过让右端点 \(-1\) 使答案变得不劣。 同理如果我们左端点 \(l\) 的元素 \(a_l\) 也要让其强制等于 \(a_r\)不然同样可以通过让左端点 \(1\) 使答案变的不劣。 所以这个性质告诉我们选中的区间 \([l,r]\) 一定满足 \(a_la_r\)。 这启发我们对于每种取值分开做 设 \(f(x)\) 是右端点为 \(x\) 时最多有多少个元素取到 \(c\) 。 考虑列出 \(DP\) 式 \(f(x)\max \left\{pre(las-1)count(las,x)suf(x1)\right\}\)其中 \(pre(i)\) 表示从 \(1\sim i\) 有多少个元素为 \(c\)同理 \(suf(i)\) 表示从 \(i\sim n\) 有多少个元素为 \(c\), \(count(l,r)\) 表示在区间 \([l,r]\) 里有多少个元素等于这个区间的端点即 \(a_r\)。 发现如果拿 \(vector\) 存的话这是一个单调队列优化 \(DP\) 的标准式子 随便优化一下就吼了 Code #includebits/stdc.h
using std::min;
using std::max;
using std::swap;
using std::vector;
typedef double db;
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pairint,int
#define all(A) A.begin(),A.end()
#define mp(A,B) std::make_pair(A,B)
const int N5e55;vectorint v[N];
int n,m,val[N],vis[N],q[N],hd;
int pre[N],suf[N],tot[N],tail;int getint(){int X0,w0;char chgetchar();while(!isdigit(ch))w|ch-,chgetchar();while( isdigit(ch))XX*10ch-48,chgetchar();if(w) return -X;return X;
}signed main(){ngetint(),mgetint();for(int i1;in;i)val[i]getint(),pre[i]pre[i-1](val[i]m),v[val[i]].pb(i);for(int in;i;i--)suf[i]suf[i1](val[i]m);int ans0;for(int i1;in;i){if(!vis[val[i]]){vis[val[i]]1;hd1,tail0;for(int j0;jv[val[i]].size();j){while(hdtail and pre[ v[ val[i] ][ j ] -1 ]-jpre[ v[ val[i] ][ q[tail] ] -1 ]-q[tail]) tail--;q[tail]j;if(hdtail) ansmax(ans,pre[ v[ val[i] ][ q[hd] ] -1 ]j-q[hd]1suf[ v[ val[i] ][ j ] 1 ]);}}} printf(%d\n,ans);return 0;
}转载于:https://www.cnblogs.com/YoungNeal/p/10142992.html
