codeforces 981D (dp+ greedy)

本文主要是介绍codeforces 981D (dp+ greedy)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目网址http://codeforces.com/problemset/problem/981/D

 题意是：将n个数字分成k个区间，每个区间和的 & 值，最大

 

dp的方法非常明显；

dp[i][k] = check ( dp[i] [k] , dp[j-1] [ k-1]  + 区间（i ，j）)

但是我们如何判断转移呢？

事实上应该是这样的，我们从最高位开始枚举1此位是否为1，可以的话，就更新答案，

那么判断是否可以的条件为，当前可以找到区间，使得，各个区间与当前答案相与并且始终为答案。仔细思考一下，我们因为是从最高位开始一位一位的往答案上加，这样保证答案一定是最优的，并且我们通过一位一位的加，可以保证，（区间和）&ans == ans

是可以判断当前方案是否可行的

  思路借鉴于https://blog.csdn.net/stupid_turtle/article/details/80488300

代码如下：

 （注意最高位不是50，因为2^50的数相与时会大于2^50）

#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>using namespace std;
const int maxn = 50+5;
long long sum[maxn];
int dp[maxn][maxn];
int n,K;
int oj(long long x)
{memset(dp,0,sizeof(dp));dp[0][0] = 1;for(int k=1; k<=K; k++)for(int i=1; i<=n; i++)for(int j=1; j<=i; j++){if(((sum[i]-sum[j-1])&x)==x && dp[j-1][k-1])dp[i][k] = 1;}return dp[n][K];
}
int main()
{scanf("%d%d",&n,&K);long long cnt = 0;sum[0] = 0;for(int i=1; i<=n; i++){scanf("%lld",&cnt);sum[i] = sum[i-1] + cnt;}long long ans = 0;for(int i=60 ;i>=0; i--){if(oj(ans|(1LL<<i)))ans|=(1LL<<i);}printf("%lld\n",ans);return 0;
}

 

这篇关于codeforces 981D (dp+ greedy)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---