数位 DP 与 区间 DP 的结合
$\text{popcount}(x)$ 的贡献是很好拆开的，我们显然可以按照每一位进行 DP。但是还需要满足升序。我们尝试从低位向高位填，每一段的后面一段在当前位上加上 $1$，容易满足升序的限制。更进一步的，我们发现这个过程形如一个区间 DP，每次将当前位为 $0$ 的 $[l,mid]$ 与当前位为 $1$ 的 $[mid+1,r]$ 合并起来，贡献就是 $\sum_{i=1}^r a_i-\sum_{i=1}^{mid} a_i$。但还需要满足值域的限制，我们参照已往数位 DP 时的做法，设新的一维表示前面还未填的 $k-i$ 位是否将 $m$ 卡满。所以设计状态 $f(i,l,r,0/1)$ 意义如上，直接转移即可。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=200+10,K=61;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
ll m;
ll a[N];
ll f[K+5][N][N][2];
inline void ckmax(ll &x,ll y){x=x>y?x:y;}
int main()
{
read(n,m);
for(int i=1;i<=n;i++)read(a[i]),a[i]+=a[i-1];
memset(f,-0x3f,sizeof(f));
for(int i=0;i<=n;i++)f[0][i][i][0]=f[0][i][i][1]=0;
for(int i=0;i<=K;i++)for(int l=1;l<=n+1;l++)f[i][l][l-1][0]=f[i][l][l-1][1]=0;
for(int i=1;i<=K;i++)
for(int l=1;l<=n;l++)
for(int r=l;r<=n;r++)
for(int t=0;t<2;t++)
if(!(m>>(i-1)&1)&&t)f[i][l][r][t]=f[i-1][l][r][t];
else for(int k=l-1;k<=r;k++)ckmax(f[i][l][r][t],f[i-1][l][k][0]+f[i-1][k+1][r][t]+a[r]-a[k]);
printf("%lld\n",f[K][1][n][1]);
return 0;
}
|