[数据结构与算法]Codeforces 981D Bookshelves & 981E Addition on Segments 两道皆是dp

981D Bookshelves

题意

长度为$n$的序列,从左到右分为$k$段,每段求和后计算二进制与,问计算出的最大值.
$n\le 50,a_i\le 2^{50}$.

题解

考虑$dp$.
不太好直接$dp$,但是由于二进制数最高位起决定作用的性质,我们考虑按位$dp$,从最高位向下枚举,每次判断$n$个数是否可以分成$k$段,使得这$k$段的和按位与之后在第$i$位能得到$1$.
令$d{p}_{ij}$表示前$i$个数是否能够分成$j$段满足条件,枚举$l\in [1,i?1]$,如果$1\to l$能分成$j?1$段,则成立,代码为dp[i][j]|=dp[l][j-1]&&(sum[i]-sum[l]&x)==x;
在枚举后面的位数的时候,我们必须要把前面几位的判断也加上.
谢谢大家.

#include<bits/stdc++.h> //Ithea Myse Valgulious
using namespace std;
ll a[59],dp[59][59];
int main() {
  ll n,k,i;
  read(n),read(k);
  for (i=1;i<=n;++i) read(a[i]),a[i]+=a[i-1];
  auto ck=[&](ll x) {
    int i,j,l;
    memset(dp,0,sizeof dp),**dp=1;
    for (i=1;i<=n;++i) 
      for (j=1;j<=k;++j)
        for (l=i-1;~l;--l) 
          dp[i][j]|=dp[l][j-1]&&(a[i]-a[l]&x)==x;
    return dp[n][k];
  };
  ll zw=0;
  for (i=59;~i;--i) 
    zw|=ck(zw|1ll<<i)?1ll<<i:0;
  printf("%lld\n",zw);
}

981E Addition on Segments

题意

一开始整个序列均为$0$,有一些区间加操作,问进行这些操作中的一部分能得到的全局最大值在$[1,n]$有哪些.

题解

考虑$dp$.
将操作按左端点排序,令$d{p}_i$表示最大值$i$最远可以在哪个位置取到.
则本题变为一道背包,最终$[1,n]$中值不为$0$的全部都是答案.

#include<bits/stdc++.h> //Ithea Myse Valgulious
using namespace std;
const int yuzu=1e5;
typedef int fuko[yuzu|10];
struct lo {
  int l,r,v;
  void rd() {
    read(l),read(r),read(v);
  }
}g[yuzu];
fuko dp;
int main() {
  int n,m,i,j;
  read(n),read(m);
  for (i=0;i<m;++i) g[i].rd();
  sort(g,g+m,[&](lo a,lo b){return a.l<b.l;});
  for (*dp=yuzu,i=0;i<m;++i) {
    for (j=n-g[i].v;~j;--j)
      dp[j]>=g[i].l?dp[j+g[i].v]=max(dp[j+g[i].v],min(dp[j],g[i].r)):0;
  }
  vector<int> zw;
  for (i=1;i<=n;++i) if (dp[i]) zw.push_back(i);
  printf("%d\n",zw.size());
  for (int p:zw) printf("%d ",p);
}

谢谢大家.