宿州网站建设开发公司哪家好,google首页,长治网站制作的流程,贵州桥梁集团建设有限公司网站传送门
题意#xff1a; 给一个长为nnn的数组(nnn为奇数)#xff0c;iii与i−1i-1i−1相邻#xff0c;111与nnn相邻#xff0c;每次选择一个位置#xff0c;将这个位置的值变成与它相邻的两个位置的和#xff0c;让后将相邻位置删掉。求最终剩下一个数的时候最大值是多少…传送门
题意 给一个长为nnn的数组(nnn为奇数)iii与i−1i-1i−1相邻111与nnn相邻每次选择一个位置将这个位置的值变成与它相邻的两个位置的和让后将相邻位置删掉。求最终剩下一个数的时候最大值是多少。
思路 首先贪心是不行的不能每次选最小的哪个把它替换成相邻的和。 由于nnn为奇数所以要取最大值的话一定是选择了n12\frac{n1}{2}2n1个数在破环成链后一定是n12\frac{n1}{2}2n1个互不相邻的数比如一下序列 1 2 3 4 5 1 2 3 4 5 选n12\frac{n1}{2}2n1个数的总情况为 1 3 5 2 4 1 3 5 2. 4 1 3 5 2 4. 显然这个式子可以分奇偶来做我们利用滑动窗口来滑就好啦。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
int a[N];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);LL sum0,t0;LL ans0;scanf(%d,n);for(int i1;in;i) scanf(%d,a[i]),suma[i],t(i%21)*a[i];ansmax(ans,t);//首先是全奇数即1与n相邻for(int i2;in;i){tsum-ta[i-1];ansmax(ans,t);}printf(%lld\n,ans);return 0;
}
/**/
