Sophie开关灯

View Submit Statistics Clarify
总Time Limit: 5000ms 单个测试点时间限制: 1000ms Memory Limit: 65536kB
Description
Sophie手里有一盏灯和一个时间序列t[1…N](保证t[1] < t[2] < … < t[N])

在T=0时刻灯被打开,然后T=t[1]时刻关闭,T=t[2]时刻打开,T=t[3]时刻关闭…直到T=M时刻。

那么在T=[0,M]这段时间内,亮灯时间就能被计算出来。

Sophie现在有一次修改序列t[1…N]的机会:她可以在序列中插入一个值,并且仍然保持序列中相邻元素的‘<’关系。

请问修改之后,在[0,M]时段中亮灯时间的最大值,特别地:Sophie也可以选择不使用这次机会。

例如M = 10,时间序列[4,6,7],则[0,4]、[6,7]这两个时段为亮灯时间;

若将序列改为[3,4,6,7],则亮灯时段为[0,3]+[4,6]+[7,10] = 8,为最长亮灯时间。

Input
第一行2个整数N,M
第二行N个正整数代表时间序列,保证严格升序
Output
输出一个正整数,代表最长亮灯时间
Sample Input
#1:
3 10
4 6 7

#2:
2 12
1 10

#3:
2 7
3 4
Sample Output
#1:
8

#2:
9

#3:
6

#include <iostream>
using namespace std;
int main() {
	int n, m, ca;
	cin >> n >> m;
	int a[n + 3] = {0}, b[n + 3] = {0}, t[n + 3]; 
	int sumj = 0, sumo = 0, num = 1;
	t[0] = 0;
	t[n + 1] = m;
	for(int i = 1; i <= n; i++) cin >> t[i];
	for(int i = 1; i <= n + 1; i++) {
		if(i % 2 == 1) sumj += t[i] - t[i - 1];
		else sumo += t[i] - t[i - 1];
	}
	b[0] = sumo;
	for(int i = 1; i <= n + 1; i++) {
		if(i % 2 == 1) {
			a[i] = a[i - 1] + t[i] - t[i - 1];
			b[i] = b[i - 1]; 
		}
		else {
			a[i] = a[i - 1];
			b[i] = b[i - 1] - t[i] + t[i - 1];
		}
	}
	int maxn = sumj;
	for(int i = 1; i <= n + 1; i++) {
		maxn = max(maxn, a[i] + b[i] - 1);
	}
	cout << maxn << endl;	
	return 0;
}