就我不会 *3500 /kel
题目描述
here。
题解
做法考虑从高位往低位处理，由于有限制的数它的值数确定的，没限制的数值不需要管，因为肯定可以是答案为 \(0\)。
所以我们考虑区间 DP，我们令 \(f_{i,l,r,0/1,0/1}\) 表示从高往低到第 \(i\) 位，最左侧 \(l\) 还有限制，第一个 \(0/1\) 表示 \(x_l\) 在上界还是下界，最右侧 \(r\) 还有限制，第二个 \(0/1\) 表示 \(x_r\) 是上界还是下界。
合并时相当于某一个数限制被解除，算一下这一位的贡献即可。
代码
记录。
#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
const int N = 55;
int n, k;
ll a[N], b[N], c[N], f[N][N][N][2][2], ff[N][N][N][2][2][2][2];
signed main() {
// freopen("xor.in", "r", stdin);
// freopen("xor.out", "w", stdout);
read(n), read(k);
F(i, 1, n) read(a[i]), read(b[i]);
F(i, 0, k - 1) read(c[i]);
ms(f, 0x3f), ms(ff, 0x3f);
F(i, 0, n) f[k][i + 1][i][1][1] = f[k][i + 1][i][1][0] = f[k][i + 1][i][0][1] = f[k][i + 1][i][0][0] = 0;
DF(i, k - 1, 0) {
F(l, 1, n + 1)
F(r, l - 1, n)
F(a, 0, 1)
F(b, 0, 1) F(aa, 0, 1) F(bb, 0, 1) {
ll A = (a ? ::a[l - 1] : ::b[l - 1]), B = (b ? ::a[r + 1] : ::b[r + 1]);
ll val = 0;
if (l != 1 && r != n) val = (((A >> i) & 1) ^ ((B >> i) & 1) ^ aa ^ bb) * c[i];
ff[i][l][r][a][b][aa][bb] = f[i + 1][l][r][a][b] + val;
}
F(len, 1, n)
for (int l = 1, r = len; r <= n; l++, r++)
F(mid, l - 1, r - 1)
F(a, 0, 1)
F(b, 0, 1)
F(c, 0, 1) F(aa, 0, 1) F(bb, 0, 1) {
if ((::a[mid + 1] >> (i + 1)) != (::b[mid + 1] >> (i + 1)) && ((b && !((::a[mid + 1] >> i) & 1)) || (!b && ((::b[mid + 1] >> i) & 1))))
chkmin(ff[i][l][r][a][c][aa][bb], ff[i][l][mid][a][b][aa][1] + ff[i][mid + 2][r][b][c][1][bb]);
}
F(l, 1, n + 1)
F(r, l - 1, n)
F(a, 0, 1)
F(b, 0, 1)
f[i][l][r][a][b] = ff[i][l][r][a][b][0][0];
}
F(len, 1, n)
for (int l = 1, r = len; r <= n; l++, r++)
F(mid, l - 1, r - 1)
F(a, 0, 1)
F(b, 0, 1)
F(c, 0, 1)
chkmin(f[0][l][r][a][c], f[0][l][mid][a][b] + f[0][mid + 2][r][b][c]);
cout << min(min(f[0][1][n][1][0], f[0][1][n][1][1]), min(f[0][1][n][0][0], f[0][1][n][0][1]));
return 0;
}