https://codeforces.com/problemset/problem/1000/B
题意：
一个模拟思维题。就是有一盏灯，0时刻开着。n次操作，你可以在其中加入一次操作（或者不加），操作为：a[i]时刻按一下开关，状态变为相反状态（开->关or关->开）。问灯亮着的时长最长为多少？
样例一0~4开（时长为4-0），4~6关（时长为6-4），6~7开（时长为7-6），7~10关（时长为10-7），可以这这些时间点中加操作使开灯时间变长 在3处加操作，开灯时长变为0～3（开）3～4（关）4～6（开）6～7（关）7～10（开）
给定n个数，和上界m，即在0到m个区间内插入n个数，形成n+1个区间，区间长度提取出来单独成一个序列。
可以选择其中至多一个数分裂，（x=y+z），求分裂后的奇数序和（tim[1]+tim[3]+....）问最大化是多少。
注意在拆分是，n如果要拆，肯定是拆成了1和n-1(n本身为1可以略过)，n-1为开灯时间
思路：
预处理加贪心
代码如下：
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <stack> 9 #include <queue> 10 #include <set> 11 #include <map> 12 #include <math.h> 13 const int INF=0x3f3f3f3f; 14 typedef long long LL; 15 const int mod=1e9+7; 16 //const double PI=acos(-1); 17 #define Bug cout<<"---------------------"<<endl 18 const int maxn=1e5+10; 19 using namespace std; 20 21 int A[maxn];//原数组 22 int p[maxn];//差分数组求差值 23 int sum[2];//辅助数组 24 int bhd_sum[maxn];//从后往前到i处的奇偶项之和 25 int fot_sum[maxn];//从前往后到i处的奇偶项之和 26 27 int main() 28 { 29 int n,m; 30 scanf("%d %d",&n,&m); 31 A[0] = 0; 32 int flag = 1; 33 for(int i = 1;i <= n;i++) 34 { 35 scanf("%d",&A[i]); 36 p[i] = A[i] - A[i-1]; 37 fot_sum[i] = fot_sum[i-1] + flag*p[i]; 38 flag = !flag; 39 } 40 A[n+1] = m; 41 p[n+1] = A[n+1]-A[n]; 42 fot_sum[n+1] = fot_sum[n] + flag*p[n]; 43 int cnt = 0; 44 for(int i = n+1;i > 0;i--) 45 { 46 sum[cnt%2] += p[i]; 47 bhd_sum[i] = sum[cnt%2]; 48 cnt++; 49 } 50 int ans = bhd_sum[1]; 51 for(int i = 1;i <= n+1;i++) 52 { 53 ans = max(ans,fot_sum[i]-1 + bhd_sum[i+1]); 54 } 55 printf("%d\n",ans); 56 }
别人写的代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 #define ll long long 8 #define N 1000005 9 10 int n,m,a[N],l[N],ans=0; 11 12 int main() 13 { 14 cin>>n>>m; 15 bool flag=1; //开关 16 l[0]=0;a[0]=0; 17 for(int i=1;i<=n;i++) 18 { 19 cin>>a[i]; 20 l[i]=l[i-1]+flag*(a[i]-a[i-1]); 21 flag=!flag; //感觉超级巧妙 22 } 23 l[n+1]=l[n]+flag*(m-a[n]);//不加操作时的总时长 24 ans=l[n+1]; 25 for(int i=1;i<=n;i++) 26 { 27 ans=max(ans,l[i]+m-a[i]-(l[n+1]-l[i])-1); //相通之后太巧妙了啊！！ 28 /*m-a[i]是在这个点改变之后所有时长 29 l[n+1]-l[i] 原来总开灯时长-这点之前开灯时长=这点之后开灯时长。而改变这个点后。后面所有开灯时长变成了关灯时长 30 m-a[i]-(l[n+1]-l[i])也就是这个点 这个点改变之后所有时长- 关灯时长 =开灯时长 31 还要-1，因为 都是在点的临近点操作*/ 32 } 33 cout<<ans<<endl; 34 }