Codeforces Round #493 (Div. 2) B. Cutting 前缀和优化_动归水题

不解释，题目过水

Code:

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int maxn = 1000 + 3;

int A[maxn], n, odds[maxn], f[200][200],b;

int main()

{

    scanf("%d%d",&n,&b);

    for(int i = 1;i <= n; ++i)

    {

        scanf("%d",&A[i]);

        if(A[i] % 2 == 1) odds[i] = 1;

        odds[i] += odds[i - 1];

    }

    for(int i = 1;i <= n; ++i)

    {

        for(int k = 0;k <= b; ++k)

        {

            for(int j = 1;j < i; ++j)

            {

                int delta = abs(A[j] - A[j + 1]);

                if((odds[i] - odds[j]) * 2 != i - j) continue;

                if(k - delta >= 0) f[i][k] = max(f[i][k], f[j][k - delta] + 1);

            }

        }

    }

    printf("%d",f[n][b]);

    return 0;

}