背包

01背包，完全背包，多重背包

int dp[MAX];  //存储最后背包最大能存多少
int value[MAX], weight[MAX], number[MAX];  //分别存的是物品的价值，每一个的重量以及数量
int bag;

void ZeroOnePack(int weight, int value)  // 01背包
{
    int i;
    for (i = bag; i >= weight; i--) {
        dp[i] = max(dp[i], dp[i - weight] + value);
    }
}
void CompletePack(int weight, int value)  //完全背包
{
    int i;
    for (i = weight; i <= bag; i++) {
        dp[i] = max(dp[i], dp[i - weight] + value);
    }
}

void MultiplePack(int weight, int value, int number)  //多重背包
{
    if (bag <= number * weight)  //如果总容量比这个物品的容量要小，那么这个物品可以直到取完，相当于完全背包
    {
        CompletePack(weight, value);
        return;
    } else  //否则就将多重背包转化为01背包
    {
        int k = 1;
        while (k <= number) {
            ZeroOnePack(k * weight, k * value);
            number = number - k;
            k = 2 * k;  //这里采用二进制思想
        }
        ZeroOnePack(number * weight, number * value);
    }
}

int main() {
    int n;
    while (~scanf("%d%d", &bag, &n)) {
        int i, sum = 0;
        for (i = 0; i < n; i++) {
            scanf("%d", &number[i]);  //输入数量
            scanf("%d", &value[i]);  //输入价值
                                     //此题没有物品的重量，可以理解为体积和价值相等
        }
        memset(dp, 0, sizeof(dp));
        for (i = 0; i < n; i++) {
            MultiplePack(value[i], value[i], number[i]);  //调用多重背包,注意传参的时候分别是重量，价值和数量
        }
        cout << dp[bag] << endl;
    }
}

多重背包（单调队列优化）

const int N = 20010;
int dp[N], pre[N], q[N];//q中存的是容量
int n, m;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        memcpy(pre, dp, sizeof(dp));  // 拷贝数组(也可用滚动数组)
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 0; j < v; ++j) { // 枚举 m ≡ j (mod v)
            //{ dp[j], dp[v+j], dp[2*v+j], dp[3*v+j], ... , dp[k*v+j] } 中的最大值,可以通过维护一个单调队列来得到
            int head = 0, tail = -1; //每次入队的值是 dp[j+k*v] - k*w
            for (int k = j; k <= m; k += v) { //容量
                if (head <= tail && k - q[head] > s * v)//如果队头元素超出范围，弹出队头元素
                    ++head;
                //队列中元素的个数应该为 s+1 个，即 0 -- s 个物品 i
                while (head <= tail && pre[q[tail]] - (q[tail] - j)/v * w <= pre[k] - (k - j)/v * w)
                    --tail; //维护队列的单调性，即：尾值 >= dp[j + k*v] - k*w

                if (head <= tail) //队头元素即为最大值,注意要加上偏移量
                    dp[k] = max(dp[k], pre[q[head]] + (k - q[head])/v * w);

                q[++tail] = k;  // 若用滚动数组, 该步要上移
            }
        }
    }
    cout << dp[m] << endl;
}

有依赖的背包问题

int n, m;
int v[110], w[110];
int p;
int head[110], ne[110], val[110], tot = 0;
int f[110][110];
void addedge(int a, int b) {
    val[++tot] = b, ne[tot] = head[a], head[a] = tot;
}
void dfs(int u) {
    for (int i = head[u]; i != -1; i = ne[i]) {  //组
        int son = val[i];
        dfs(son);

        for (int j = m - v[u]; j >= 0; j--) {  //背包容量
            for (int k = 0; k <= j; k++) {     //决策
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
            }
        }
    }
    for (int i = m; i >= v[u]; i--)
        f[u][i] = f[u][i - v[u]] + w[u];
    for (int i = 0; i < v[u]; i++)
        f[u][i] = 0;
}
int main() {
    cin >> n >> m;
    memset(head, -1, sizeof head);
    int root;
    rep(i, 1, n) {
        cin >> v[i] >> w[i] >> p;
        if (p == -1)
            root = i;
        else {
            addedge(p, i);
        }
    }
    dfs(root);
    cout << f[root][m] << endl;
}

背包问题求具体方案

int n, m;
int v[1010], w[1010];
int f[1010][1010];
int main() {
    jiasu;
    cin >> n >> m;
    rep(i, 1, n) cin >> v[i] >> w[i];
    don(i, n, 1) {  // 要求输出字典序最小的方案, 需要反推
        rep(j, 0, m) {
            f[i][j] = f[i + 1][j];
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    }
    int j = m;
    rep(i, 1, n) {  // 从前往后推, 能选就选, 才能保证字典序最小
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
            cout << i << " ";
            j -= v[i];
        }
    }

    return 0;
}

求方案数初始化总结

二维情况

$1.\;体积至多为j,\;f[0][i] = 1,\;0 <= i <= m, 其余是0$

$2.\;体积恰好为j,\;f[0][0] = 1,\;其余是0$

$3.\;体积至少是j,\;f[0][0] = 1,\;其余是0$

一维情况

$1.\;体积至多为j,\;f[i] = 1,\;0 <= i <= m$

$2.\;体积恰好为j,\;f[0] = 1,\;其余是0$

$3.\;体积至少是j,\;f[0] = 1,\;其余是0$

+++

求最值初始化总结

二维情况

$1.\;体积至多为j,\;f[i][k] = 0,\;0<=i<=n,\;0<=k<=m\ \ (只会求价值的最大值)$

$2.\;体积恰好为j,\;$

$\ \ \ \ 当求价值的最小值:\ f[0][0] = 0,\ 其余是INF$

$\ \ \ \ 当求价值的最大值:\ f[0][0] = 0,\ 其余是-INF$

$3.\;体积至少为j,\ f[0][0] = 0,\ 其余是INF\ \ (只会求价值的最小值)$

一维情况

$1.\ 体积至多为j,\ f[i] = 0,\ 0 <= i<= m\ \ (只会求价值的最大值)$

$2.\ 体积恰好为j,$

$\ \ \ \ 当求价值的最小值:\ f[0] = 0,\ 其余是INF$

$\ \ \ \ 当求价值的最大值:\ f[0] = 0,\ 其余是-INF$

$3.\ 体积至少为j,\ f[0] = 0,\ 其余是INF\ \ (只会求价值的最小值)$

+++

求方案数问题

1、从前i个物品中选，且总体积不超过j的总方案数，初始化是f[0][i] = 1, 0 <= i <= m，其余是0
// 01背包
for (int i = 0; i <= m; i++)
    f[i] = 1;
for (int i = 1; i <= n; i++) {
    int v;
    cin >> v;
    for (int j = m; j >= v; j--) {
        f[j] = f[j] + f[j - v];
    }
}

// 完全背包
for (int i = 0; i <= m; i++)
    f[i] = 1;
for (int i = 1; i <= n; i++) {
    int v;
    cin >> v;
    for (int j = v; j <= m; j++) {
        f[j] = f[j] + f[j - v];
    }
}

2、从前i个物品中选，且总体积恰好是j的总方案数，初始化是f[0][0] = 1, 其余是0
// 01背包
f[0] = 1;
for (int i = 1; i <= n; i++) {
    int v;
    cin >> v;
    for (int j = m; j >= v; j--) {
        f[j] = f[j] + f[j - v];
    }
}

// 完全背包
f[0] = 1;
for (int i = 1; i <= n; i++) {
    int v;
    cin >> v;
    for (int j = v; j <= m; j++) {
        f[j] = f[j] + f[j - v];
    }
}

3、从前i个物品中选，且总体积至少是j的总方案数，初始化是f[0][0] = 1, 其余是0（至少的情况，j需要从0枚举到m，或者从m枚举到0）
// 01背包
f[0] = 1;
for (int i = 1; i <= n; i++) {
    int v;
    cin >> v;
    for (int j = m; j >= 0; j--) {      //即使物品体积比j大，j - v < 0，也能选，等价于f[0]
        f[j] = f[j] + f[max(0, j - v)];
    }
}

状压DP

最短Hamilton路径（旅行商问题）

const int N = 20, M = 1 << N;
int f[M][N], w[N][N];  // w表示的是无权图
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> w[i][j];
    memset(f, 0x3f, sizeof(f));  //因为要求最小值，所以初始化为无穷大
    f[1][0] = 0;                 //因为零是起点,所以f[1][0]=0;
    for (int i = 0; i < 1 << n; i++)  // i表示所有的状态
        for (int j = 0; j < n; j++)   // j表示走到哪一个点
            if (i >> j & 1)
                for (int k = 0; k < n; k++)  // k表示走到j这个点之前,以k为终点的最短距离
                    if (i - (1 << j)>> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);  //更新最短距离
    cout << f[(1 << n) - 1][n - 1] << endl;  //表示所有点都走过了,且终点是n-1的最短距离
}

区间DP

棋盘分割–二维区间DP

const int N = 10, M = 16;
const double MAXN = 1e9;
int n;
int s[N][N];
double f[N][N][N][N][M], x;    // 第5维是分割为几块
double get(int x1, int y1, int x2, int y2) {
    double sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 -1 ][y1 - 1]  - x;
    return sum * sum / n;
}
double dp(int x1, int y1, int x2, int y2, int k) {    // 记忆化搜索
    auto& v = f[x1][y1][x2][y2][k];
    if (v >= 0)
        return v;
    if (k == 1)
        return v = get(x1, y1, x2, y2);
    v = MAXN;
    for (int i = x1; i < x2; i++) {
        v = min(v, dp(x1, y1, i, y2, k - 1) + get(i + 1, y1, x2, y2));
        v = min(v, get(x1, y1, i, y2) + dp(i + 1, y1, x2, y2, k - 1));
    }
    for (int i = y1; i < y2; i++) {
        v = min(v, dp(x1, y1, x2, i, k - 1) + get(x1, i + 1, x2, y2));
        v = min(v, get(x1, y1, x2, i) + dp(x1, i + 1, x2, y2, k - 1));
    }
    return v;
}
signed main() {
    cin >> n;
    rep(i, 1, 8) {
        rep(j, 1, 8) {
            cin >> s[i][j];
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    x = (double)s[8][8] / n;  // 平均值
    memset(f, -1, sizeof f);  // 初始化为nan
    cout << fixed << setprecision(3) << sqrt(dp(1, 1, 8, 8, n)) << endl;
}

树形DP

树的直径

const int N = 20010;
int head[N], ne[N], w[N], v[N], idx, n;
void add(int x, int y, int z) {
    v[++idx] = y, w[idx] = z, ne[idx] = head[x], head[x] = idx;
}
int ans = 0;
int dfs(int u, int fa) {
    int d1 = 0, d2 = 0;
    for (int i = head[u]; i; i = ne[i]) {
        int j = v[i];
        if (j == fa)
            continue;
        int val = dfs(j, u) + w[i];
        if (val > d1)
            d2 = d1, d1 = val;
        else if (val > d2)
            d2 = val;
    }
    ans = max(ans, d1 + d2);
    return d1;
}
signed main() {
    cin >> n;
    rep(i, 1, n - 1) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z), add(y, x, z);
    }
    dfs(1, 0);
    cout << ans << endl;
}

树的中心：该点到树中其他节点的最远距离最近

const int N = 10010, M = N << 1;
int head[N], ne[M], v[M], w[M], tot;
int n, d1[N], d2[N], p[N], up[N];
void add(int x, int y, int z) {
    v[++tot] = y, w[tot] = z, ne[tot] = head[x], head[x] = tot;
}
int dfs_down(int u, int fa) {  // 用子节点更新父节点的最长向下距离
    d1[u] = d2[u] = 0;
    for (int i = head[u]; i; i = ne[i]) {
        int j = v[i];
        if (j == fa)
            continue;
        int d = dfs_down(j, u) + w[i];
        if (d > d1[u])
            d2[u] = d1[u], d1[u] = d, p[u] = j;  // 表示u向下经过j时有最大距离
        else if (d > d2[u])
            d2[u] = d;
    }
    return d1[u];
}
void dfs_up(int u, int fa) {  // 用父节点更新子节点的最长向上距离
    for (int i = head[u]; i; i = ne[i]) {
        int j = v[i];
        if (j == fa)
            continue;
        if (p[u] == j)  // u向下的最长距离经过j,那么只能用次长距离(由dfs_down知一定不经过j)
            up[j] = max(up[u], d2[u]) + w[i];
        else  // 否则用最长的向下距离
            up[j] = max(up[u], d1[u]) + w[i];
        dfs_up(j, u);  // 用j更新j的子节点的最长向上距离
    }
}
signed main() {
    cin >> n;
    rep(i, 1, n - 1) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z), add(y, x, z);
    }
    dfs_down(1, 0), dfs_up(1, 0);
    int ans = INF;
    rep(i, 1, n) ans = min(ans, max(d1[i], up[i]));
    cout << ans << endl;
}

数位DP

/* 计数问题（给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。）*/
int base[10];
int f[10][10], g[10][10];
void init()
{
    base[0] = 1;
    for(int i = 1 ; i <= 9 ; i++) base[i] = base[i-1]*10;

    //从00……0 - 99……9 的各位数字有多少个，其中i为数字个数（包含前导零）
    for(int i = 0 ; i <= 9 ; i++) f[1][i] = 1;
    for(int i = 2 ; i <= 9 ; i++)
        for(int j = 0 ; j <= 9 ; j++)
            f[i][j] = f[i-1][j]*10 + base[i-1]; // base[i-1]为第i位取j, 剩下随便取的个数

    //从1 - 99……9 的各位数字有多少个，其中i为数字个数（不包含前导零）
    for(int i = 1 ; i <= 9 ; i++) g[1][i] = 1;//循环从1开始
    for(int i = 2 ; i <= 9 ; i++) {
        g[i][0] = g[i-1][0] + f[i-1][0]*9; //第i位取0, 第i-1位就不能取0了
        for(int j = 1 ; j <= 9 ; j++)
            g[i][j] = g[i-1][j] + f[i-1][j]*9 + base[i-1];
    }
}
vector<int> dp(int n) {
    vector<int> ans(10,0); //记录答案
    if(n<=0) return ans; //边界条件

    vector<int> nums;
    while(n) nums.push_back(n%10), n/=10;

    vector<int> last(10,0); //记录前缀中各个数字个数

    //统计1 - 99……9(n-1个9)里面各个数字有多少个
    for(int i = 0 ; i <= 9 ; i++) ans[i] = g[nums.size()-1][i];
    //统计大于10……0(n-1个0) 的数里各个数字有多少个
    for(int i = nums.size()-1 ; i >=0 ; i--) {
        //循环变量i可以表示剩下的数字有多少个
        int x = nums[i];
        for(int j = i==nums.size()-1 ; j < x ; j++) { //第一次循环不能有0
            //前缀部分
            for(int k = 0 ; k <= 9 ; k++)
                ans[k] += last[k] * base[i];
            //当前位置部分
            ans[j] += base[i];
            //后缀部分
            for(int k = 0 ; k <= 9 ; k++)
                ans[k] += f[i][k];
        }
        //更新前缀计数器
        last[x] ++;
        //统计叶子节点（这个数本身）
        if(!i) for(int k = 0 ; k <= 9 ; k++) ans[k] += last[k];
    }
    return ans;
}

vector<int> ask(int a, int b) {
    auto x = dp(b);
    auto y = dp(a-1);
    vector<int> ans;
    for(int i = 0 ; i <= 9 ; i++) ans.push_back(x[i]-y[i]);
    return ans;
}

/* 求0~val 第k位二进制位上1的总个数 */
ll cal(int k, ll val) {
    if (!val)
        return 0;
    ll st = (1ll << k), cycle = (1ll << (k + 1));  // 周期:从0到该位第一次为1，出现1后第一次为0
    // cycle 就是周期长度
    ll len = cycle - st;  // 一个周期中为1的长度
    ll res = val / cycle * len;
    ll m = val % cycle;  // 未满一个周期的余数
    if (m >= st)         // 该余数>=st的部分才为1
        res += m - st + 1;
    return res;
}

单调队列优化DP

n个车站，每个车站有若干升油，每升油行驶1千米，起始油量为0，每到一个车站就把油都带走，判断以每个点为起点能否周游一周

const int N = 2e6 + 10;
int n;
ll p[N], d[N], s[N], q[N];
bool st[N];
signed main() {
    jiasu;
    cin >> n;
    rep(i, 1, n) cin >> p[i] >> d[i];   // 存油量，顺时针方向到下一站的距离

    // 顺时针
    rep(i, 1, n) s[i] = s[i + n] = p[i] - d[i];
    rep(i, 1, n * 2) s[i] += s[i - 1];
    int h = 0, t = -1;
    don(i, n * 2, 1) {  // 枚举起点
        if (h <= t && q[h] >= i + n)
            h++;
        while (h <= t && s[q[t]] >= s[i])
            t--;
        q[++t] = i;
        if (i <= n) {
            if (s[q[h]] >= s[i - 1])
                st[i] = 1;
        }
    }

    // 逆时针
    d[0] = d[n];
    rep(i, 1, n) s[i] = s[i + n] = p[i] - d[i - 1];
    rep(i, 1, n * 2) s[i] += s[i - 1];
    h = 0, t = -1;
    rep(i, 1, n * 2) {  // 枚举起点
        if (h <= t && q[h] < i - n)
            h++;
        if (i > n) {
            if (s[q[h]] <= s[i])
                st[i - n] = 1;
        }
        while (h <= t && s[q[t]] <= s[i])
            t--;
        q[++t] = i;
    }
    rep(i, 1, n) {
        if (st[i])
            cout << "TAK\n";
        else
            cout << "NIE\n";
    }
}

斜率优化DP

问题：$n$个任务排成一个序列在一台机器上等待执行，他们的顺序不得改变，机器会把这$n$个任务分成若干批，从时刻 $0$ 开始，任务被分批加工，执行第$i$个 任务所需的时间是$T_i$。一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。每批任务开始前，机器需要$S$的启动时间，每个任务的费用是它的完成时刻乘费用系数$C_i$。请为机器规划一个分组方案，使得总费用最小。

状态表示：$f[i]$：前$i$个任务的最小费用

状态转移：$f[i]\ \ = \ \ min\{f[j]\ +\ t[i]\ *\ (c[i]\ -\ c[j])\ +\ s\ *\ (c[n]\ -\ c[j])\}$

提出变量：$f[i]\ \ = \ \ min\{f[j]\ -\ (t[i]\ +\ s)\ *\ c[j]\ +\ t[i]\ *\ c[i]\ +\ s\ *\ c[n]\}$

[HTML_REMOVED]  [HTML_REMOVED]即：$f[j]\ =\ (t[i]\ +\ s)\ *\ c[j]\ -\ t[i]\ *\ c[i]\ -\ s\ *\ c[n]\ +\ f[i]$

该式可类比直线的斜截式方程：$y\ =\ kx\ +b$，$f[i]$最小即为直线的截距最小，且直线与先前的点$(c[j],\ f[j]),0<=j<=i-1$形成的凸包相切的点使其截距最小

$1.$斜率单调递增，新加的点的横坐标也单调递增

[HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED]在查询的时候，可以将队头小于当前斜率的点全部删掉。

[HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED]在插入的时候，将队尾不在凸包上的点全部删掉。

const int N = 3e5 + 10;
int n, s;
ll t[N], c[N];
ll f[N];
int q[N];
signed main() {
    jiasu;
    cin >> n >> s;
    rep(i, 1, n) {
        int x, y;
        cin >> x >> y;
        t[i] = t[i - 1] + x;
        c[i] = c[i - 1] + y;
    }
    int hh = 0, tt = 0;
    rep(i,1,n) {
        while(hh < tt && f[q[hh + 1]] - f[q[hh]] <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]]))
            hh++;  // 队头斜率小于当前斜率的点出队
        int j = q[hh];
        f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];  // 第一个斜率的大于当前斜率的左端点
        while(hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (f[i] - f[q[tt]]) * (c[q[tt]] - c[q[tt - 1]]))
            tt--;  // 凸包的边界斜率单调递增
        q[++tt] = i;
    }
    cout << f[n] << endl;
}

$2.$当$t_i$可以小于$0$时，斜率不再具有单调性，但新加的点的横坐标一定单调递增。

[HTML_REMOVED]  在查询的时候，只能二分来找。

[HTML_REMOVED]  在插入的时候，将队尾不在凸包上的点全部删掉。

const int N = 3e5 + 10;
int n, s;
ll t[N], c[N];
ll f[N];
int q[N];
signed main() {
    jiasu;
    cin >> n >> s;
    rep(i, 1, n) {
        cin >> t[i] >> c[i];
        t[i] += t[i - 1];
        c[i] += c[i - 1];
    }
    int hh = 0, tt = 0;
    rep(i,1,n) {
        int l = hh, r = tt;
        while(l < r) {
            int mid = l + r >> 1;
            if((f[q[mid + 1]] - f[q[mid]]) > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]]))
                r = mid;
            else
                l = mid + 1;
        }
        int j = q[r];
        f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];  // 第一个斜率的大于当前斜率的左端点
        while(hh < tt && (double)(f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (double)(f[i] - f[q[tt]]) * (c[q[tt]] - c[q[tt - 1]]))
            tt--;  // 凸包的边界斜率单调递增
        q[++tt] = i;
    }
    cout << f[n] << endl;
}