关于边界
查看原帖
关于边界
515891
paper_楼主2024/11/20 10:34

为什么在第 1717 行加上 r <= l + (1ll << i - 1),会出错?理论上 02k0 \sim 2^k 只能覆盖 2k+12^k + 1 个点,因为 bib_i 互不相同。

#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;
}
2024/11/20 10:34
加载中...