Bookshelves

wjh15101051's space

卧薪尝胆，厚积薄发。

Bookshelves

Date: Thu Sep 20 21:11:34 CST 2018

In Category: NoCategory

Description：

把一个长为 $n$ 的序列划分成 $k$ 段，最大化每段和的 $\text{and}$ 和。

$1\le n,k \le 50$

Solution：

按位贪心 $DP$ 验证的套路，从高到低枚举每一位，这一位可以为一当且仅当所有区间和这一位都为一，且所有区间和的更高位都满足之前的限制， $n$ 和 $k$ 都很小 $DP$ 就行了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 60

typedef long long ll;

ll a[MAXN];

bool f[MAXN][MAXN];

ll sum[MAXN];

int main()

{

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

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

	{

		scanf("%lld",&a[i]);

		sum[i] = sum[i - 1] + a[i];

	}

	ll val = 0;

	for(ll b = 62;b >= 0;--b)

	{//cout << b << " : " << endl;

		memset(f,false,sizeof(f));

		f[0][0] = true;

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

		{

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

			{

				for(int l = 0;l < i;++l)

				{

					if((((sum[i] - sum[l]) & (1ll << b))) != 0 && (((sum[i] - sum[l]) & val) == val))

					{

						f[i][j] |= f[l][j - 1];

					}

				}

			}

		}

		if(f[n][k])val |= (1ll << b);

	}

	cout << val << endl;

	return 0;

}

In tag: 算法-贪心 DP-DP

wjh15101051