问题描述

在小蓝面前有 nn 个方格，每个方格里面都有一颗糖果，糖果的口味有两种，一种是芒果味，一种是蓝莓味。小蓝每次都可以向前跳跃一格或两格，每到一个方格，小蓝就会将方格上的糖果吃下去。如果小蓝吃到的糖果是芒果味，心情值就会减少 11 点；如果小蓝吃到的糖果是蓝莓味，心情值就会增加 11 点，小蓝的初始心情值为 00。

现在问你，是否存在一种跳跃方式，使得小蓝 跳跃出所有方格 后，心情值恰好为 xx 点。如果存在，则输出 Yes；如果不存在，则输出 No。

对于跳跃出所有方格的解释：

图片描述

小蓝初始在 00 位置，需要跳跃到终点 n+1n+1。

输入格式

第一行输入一个正整数 tt，表示测试用例组数。（1≤t≤10001≤t≤1000）。

对于每组测试数据：

第一行输入两个正整数 n,xn,x，含义如题所述。（1≤n≤2×105,−2×105≤x≤2×1051≤n≤2×105,−2×105≤x≤2×105）。

第二行输入 nn 个整数，第 ii 个整数的值为 11 或 −1−1，11 代表该位置是蓝莓味的糖果，−1−1 代表该位置是芒果味的糖果。（1≤i≤n1≤i≤n）。

1≤∑i=1tni≤2×1051≤∑i=1t​ni​≤2×105。

输出格式

对于每组测试数据，若存在一种跳跃方式，使得小蓝跳跃出方格后，心情值恰好为 xx 点，则输出 Yes；如果不存在，则输出 No。

正解

如果所有路线方案里面的最小值和最大值包含 xx，则存在一种调整方案可以变成 xx。

然后设所有的走法里方案里最小值是 LL, 最大值是 RR。

将最小值路径调整最大值路径的过程中，走到 −1−1 的位置变成走到 11 的位置， 多走一些 11, 减少一些 −1−1 ，在每次调整过程中，结果都只会 + 1或 +2，所以 LL ~ RR 都是可以被调整取到。

最后求这个最大最小值用一个非常简单的动态规划就行了。

#include<bits/stdc++.h>
#define int long long
const int N = 2e5+20;
using namespace std;
int t;
int n,x;
int a[N],f[N],g[N];

signed main()
{
  cin>>t;
  while(t--)
  {
    cin>>n>>x;
    memset(a,0,sizeof a);//记得一定要重置a数组
    for(int i = 1;i<=n;i++)cin>>a[i];

    f[1] = g[1] = a[1];

    for(int i = 2;i<=n+1;i++)
    {
      f[i] = max(f[i-1],f[i-2]) + a[i];
      g[i] = min(g[i-1],g[i-2]) + a[i];
    }
    if(x >= g[n+1] && x <= f[n+1])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
  return 0;
}