牛客寒训营6 B (雀氏没有绿名的水平)

题目 题意: 给定长度为n的数组a，求有多少子序列的价值与整个数组的价值相同。(均为正整数)  价值: Sigma 1到n-1 |a[i] - a[i+1]|. 长度为1的子序列的价值规定为0。 思路: 样例给了很多暗示。对于一段相同的数的区间，删一删不打紧。但是要注意，能不能全删呢？ 假设他不是波峰或者波谷，不能全删。Cn0 + Cn1 + … Cnn - 1 = 2^n - 1. 否则全删也无妨. 如果是波峰或者波谷，与b无关。 时间复杂度: O(n) 代码:

// Problem: 价值序列
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23481/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i>= 1;
	}
	return res;
}
void solve()
{
   read(n);
   vector a(n+2);
   vector va;
   for(int i=1;i