$\quad$常规做法，应该是排序，然后贪心。中间的正确性，可以直接证明。

$\quad$赛时，没有第一时间考虑贪心的做法，考虑的是记忆化搜索。但是碰到了几个问题。

$\quad$记忆化搜索 , 定义$dfs( l , r , k)$:为将$[l , r ]$这一子段通过最多花费$k$对情况下，最多能分割多少次。

$\quad$状态转移：$dfs(l , r , k ) = max \{ dfs(l , i ) \} _{i = l + 1 }^{ i = r }$

$\quad$碰到了几个问题，中间尝试过单独枚举，每一种可能的花费。

$\quad$实际上这是误解，因为在状态转移的过程中，会自动把所有可能的状态找到，而不需要再单独枚举可能的花费。因此这样做，会使得，时间复杂度由原来的$O(n * n * k )$ 变为$O(n * n * k * k)$

Code

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int dp[101][101][101];
int a[110] ,sum[110];
int cnt;
int dfs(int  l , int  r , int  cost)
{



    int & res = dp[l][r][cost];
    if(res != -1 )return res;

    res = (sum[r] - sum[l - 1 ]?-inf:0);

    for(int i = l + 1; i < r - 1 ; i +=2)
    {
        int dif = abs(a[i + 1] - a[i]);
        if(cost >= dif)
        {
            dfs(l , i , cost - dif);
            if(dp[l][i][cost - dif] >= 0 && sum[r] - sum[i] == 0)res = max(res , dp[l][i][cost - dif] + 1);
        }

    }
    return res;
}
void solve()
{
   int n ; cin>>n;
   int B ; cin>>B;
   memset(dp , -1 ,sizeof dp);
   for(int i = 1 ; i <= n ; i++)cin>>a[i];

   for(int i = 1 ; i <= n ; i++)sum[i] = sum[i - 1 ] + (a[i]%2?1:-1);


   cout<<dfs(1 , n , B)<<endl;
   return ;
}
signed main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        solve();
        return 0;
}