AKSZ-区间DP
2024-07-07 17:32:24
发布于:广东
区间DP
P2858 [USACO06FEB] Treats for the Cows G/S
for(int len = 1; len <= n; len++)
{
for(int beg = 1; beg <= n; beg++)
{
int j;
j = i + len - 1;
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) + sum[i] + sum[j - 1];
}
}
使小区间在大区间之前计算
P1775 石子合并(弱化版)
OI WIKI - 四边形不等式
// +四边形不等式
for(int L = 2; L <= n; L++)
{
for(int i = 1, j = L; j <= n; i++, j++)
{
for(int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++)
{
if (dp[i][j] > dp[i][k] + dp[k + 1][j] + w(i, j)) {
dp[i][j] = dp[i][k] + dp[k + 1][j] + w(i, j);
opt[i][j] = k; // 决策点
}
}
// printf("%d %d %lld\n", i, j, dp[i][j]);
}
}
进制转换
10 -> other
整数
除(进制)取余,逆序排列
小数
乘(进制)取整,顺序排列
other -> 10
按权展开法
例:
位运算
常见位运算
按位与 & 低位对齐,高位补0,当相应二进制位都为1时,结果的相应位为1,其余为0 x&(x-1)是否为2的幂次
按位或 | 当两个相应二进制位为0,结果为0,其余为1
按位非 ~ 将二进制的每一位取反 ~-1 = 0
按位异或 ^ 相同为0,不同为1 a^b^a=a^a^b=b
按位左移 << <<a 将二进制数左移a位,高位丢弃,低位补0 a<<b a×2^b
按位右移 >> >>a 将二进制数右移a位,高位补0,低位丢弃 a>>b a÷2^b
运算优先级
1. ~
2. << >>
3. &
4. ^
5. |
原码/反码/补码
原码
数值前增加一位符号位
反码
正数的反码:与原码相同
负数的反码:在原码的基础上,除符号位外取反
补码
正数的补码:与原码、反码相同
负数的补码:在反码的基础上加1(溢出部分舍弃)
计算机存储
1 Byte = 8 bit
图片大小
位图:
容量 = 宽度 * 高度 * 位深度 / 8
这里空空如也
有帮助,赞一个