为什么在第 17 行加上 r <= l + (1ll << i - 1)
,会出错?理论上 0∼2k 只能覆盖 2k+1 个点,因为 bi 互不相同。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 210;
int dp[61][N][N][2];
int n, m, a[N], sum[N];
signed main() {
cin >> n >> m;
memset(dp, -0x3f, sizeof dp);
for (int i = 1; i <= n; i ++ ) cin >> a[i], sum[i] = sum[i - 1] + a[i], dp[0][i][i][0] = dp[0][i][i][1] = 0;
for (int i = 0; i <= 60; i ++ )
for (int j = 1; j <= n + 1; j ++ )
dp[i][j][j - 1][0] = dp[i][j][j - 1][1] = 0;
for (int i = 1; i <= 60; i ++ ) {
int u = m >> i - 1 & 1;
for (int l = 1; l <= n; l ++ )
for (int r = l; r <= n; r ++ ) {
for (int k = l - 1; k <= r; k ++ ) {
if (u) dp[i][l][r][1] = max(dp[i][l][r][1], dp[i - 1][l][k][0] + dp[i - 1][k + 1][r][1] + sum[r] - sum[k]);
dp[i][l][r][0] = max(dp[i][l][r][0], dp[i - 1][l][k][0] + dp[i - 1][k + 1][r][0] + sum[r] - sum[k]);
}
if (!u) dp[i][l][r][1] = dp[i - 1][l][r][1];
}
}
cout << dp[60][1][n][1];
return 0;
}