首页 > 其他分享 >三维动态规划

三维动态规划

时间：2024-02-01 15:55:06浏览次数：45  
标签：return recursive int s2 s1 三维 动态 规划 dp

三维动态规划

474. 一和零

  • 多维费用背包
int zeros;
int ones;
int len;

void count(char *s) {
    zeros = 0;
    ones = 0;
    int l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (s[i] == '0') zeros++;
        if (s[i] == '1') ones++;
    }
}

int max(int a, int b) {
    return a > b ? a : b;
}

// 返回0不超过z，1不超过o时，strs从curIndex下标往后选，最大的子集长度
int recursive(char **strs, int curIndex, int z, int o) {
    if (curIndex == len) return 0;
    // 不选中
    int p1 = recursive(strs, curIndex + 1, z, o);
    // 选中strs[curIndex]
    int p2 = 0;
    count(strs[curIndex]);
    if (zeros <= z && ones <= o)
        p2 = 1 + recursive(strs, curIndex + 1, z - zeros, o - ones);
    return max(p1, p2);
}

// 暴力超时
int findMaxForm(char **strs, int strsSize, int m, int n) {
    len = strsSize;
    return recursive(strs, 0, m, n);
}

int zeros;
int ones;
int len;

void count(char *s) {
    zeros = 0;
    ones = 0;
    int l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (s[i] == '0') zeros++;
        if (s[i] == '1') ones++;
    }
}

int max(int a, int b) {
    return a > b ? a : b;
}

int ***dp;

// 返回0不超过z，1不超过o时，strs从curIndex下标往后选，最大的子集长度
int recursive(char **strs, int curIndex, int z, int o) {
    if (curIndex == len) return 0;
    if (dp[curIndex][z][o] != -1) return dp[curIndex][z][o];
    // 不选中
    int p1 = recursive(strs, curIndex + 1, z, o);
    // 选中strs[curIndex]
    int p2 = 0;
    count(strs[curIndex]);
    if (zeros <= z && ones <= o)
        p2 = 1 + recursive(strs, curIndex + 1, z - zeros, o - ones);
    int res = max(p1, p2);
    dp[curIndex][z][o] = res;
    return res;
}

// 自上而下记忆化搜索
int findMaxForm(char **strs, int strsSize, int m, int n) {
    len = strsSize;
    dp = (int ***) malloc(sizeof(int **) * len);
    for (int i = 0; i < len; ++i)
        dp[i] = (int **) malloc(sizeof(int *) * (m + 1));
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j <= m; ++j) {
            dp[i][j] = (int *) malloc(sizeof(int) * (n + 1));
            memset(dp[i][j], -1, sizeof(int) * (n + 1));
        }
    }
    return recursive(strs, 0, m, n);
}

int zeros;
int ones;

void count(char *s) {
    zeros = 0;
    ones = 0;
    int l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (s[i] == '0') zeros++;
        if (s[i] == '1') ones++;
    }
}

int max(int a, int b) {
    return a > b ? a : b;
}

// 自底向上
int findMaxForm(char **strs, int strsSize, int m, int n) {
    // 返回0不超过z，1不超过o时，strs从curIndex下标往后选，最大的子集长度
    int dp[strsSize + 1][m + 1][n + 1];
    // 最上层strsSize层全0，即strs从strsSize下标往后选，最大的子集长度是0，因为没有字符串可选
    for (int i = 0; i <= m; ++i)
        for (int j = 0; j <= n; ++j)
            dp[strsSize][i][j] = 0;
    // 从strsSize-1层往下填写每个二维表
    for (int curIndex = strsSize - 1; curIndex >= 0; curIndex--) {
        count(strs[curIndex]);
        // 当前层只依赖与上层的元素
        for (int z = 0, p1, p2; z <= m; ++z) {
            for (int o = 0; o <= n; ++o) {
                p1 = dp[curIndex + 1][z][o];
                p2 = 0;
                if (zeros <= z && ones <= o)
                    p2 = 1 + dp[curIndex + 1][z - zeros][o - ones];
                dp[curIndex][z][o] = max(p1, p2);
            }
        }
    }
    return dp[0][m][n];
}


int zeros;
int ones;

void count(char *s) {
    zeros = 0;
    ones = 0;
    int l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (s[i] == '0') zeros++;
        if (s[i] == '1') ones++;
    }
}

int max(int a, int b) {
    return a > b ? a : b;
}

// 空间压缩
int findMaxForm(char **strs, int strsSize, int m, int n) {
    // 返回0不超过z，1不超过o时，strs从curIndex下标往后选，最大的子集长度
    int dp[m + 1][n + 1];
    // 最上层strsSize层全0，即strs从strsSize下标往后选，最大的子集长度是0，因为没有字符串可选
    for (int i = 0; i <= m; ++i)
        memset(dp[i], 0, sizeof(int) * (n + 1));
    // 从strsSize-1层往下填写每个二维表（实际上和遍历字符串的顺序无关）
    for (int i = strsSize - 1; i >= 0; i--) {
        count(strs[i]);
        // 当前层只依赖与上层的元素，从上往下，从右往左更新当前层，这样左下角尚未跟新的元素实际就是上一层的元素
        // 依赖于上一层同一位置的元素和上一层同一位置的左下角区域的所有元素
        for (int z = m; z >= zeros; z--)
            for (int o = n; o >= ones; o--)
                dp[z][o] = max(dp[z][o], dp[z - zeros][o - ones] + 1);
    }
    return dp[m][n];
}

879. 盈利计划

  • 多维费用背包
int *g;
int *p;
int gSize;
const int MOD = 1e9 + 7;

// 到i号工作，人数还剩r，利润还有s才达标
int recursive(int r, int s, int i) {
    // 人数用尽，判断利润是否达标
    if (r <= 0) return s <= 0 ? 1 : 0;
    // 工作用尽，判断利润是否达标
    if (i == gSize) return s <= 0 ? 1 : 0;
    // 情况1：要当前工作
    int p1 = recursive(r, s, i + 1);
    // 情况2：不要当前工作
    int p2 = 0;
    if (g[i] <= r)
        p2 = recursive(r - g[i], s - p[i], i + 1);
    return (p1 + p2) % MOD;
}

// 暴力超时
int profitableSchemes(int n, int minProfit, int *group, int groupSize, int *profit, int profitSize) {
    p = profit;
    g = group;
    gSize = groupSize;
    return recursive(n, minProfit, 0);
}

int *g;
int *p;
int gSize;
const int MOD = 1e9 + 7;
int ***dp;

int max(int a, int b) {
    return a > b ? a : b;
}

// 到i号工作，人数还剩r，利润还有s才达标
int recursive(int r, int s, int i) {
    // 人数用尽，判断利润是否达标
    if (r <= 0) return s <= 0 ? 1 : 0;
    // 工作用尽，判断利润是否达标
    if (i == gSize) return s <= 0 ? 1 : 0;
    if (dp[i][r][s] != -1) return dp[i][r][s];
    // 情况1：要当前工作
    int p1 = recursive(r, s, i + 1);
    // 情况2：不要当前工作
    int p2 = 0;
    // 利润达标了，但人数没耗尽，后续的可能也要计算
    // 利润变成负数或0都能表示利润达标，但是负数不在dp表的下标范围内
    if (g[i] <= r)
        p2 = recursive(r - g[i], max(s - p[i], 0), i + 1);
    dp[i][r][s] = (p1 + p2) % MOD;
    return dp[i][r][s];
}

// 自顶向下记忆化搜索
int profitableSchemes(int n, int minProfit, int *group, int groupSize, int *profit, int profitSize) {
    p = profit;
    g = group;
    gSize = groupSize;
    dp = (int ***) malloc(sizeof(int **) * groupSize);
    for (int i = 0; i < groupSize; ++i)
        dp[i] = (int **) malloc(sizeof(int *) * (n + 1));
    for (int i = 0; i < groupSize; ++i) {
        for (int j = 0; j <= n; ++j) {
            dp[i][j] = (int *) malloc(sizeof(int) * (minProfit + 1));
            memset(dp[i][j], -1, sizeof(int) * (minProfit + 1));
        }
    }

    return recursive(n, minProfit, 0);
}

int max(int a, int b) {
    return a > b ? a : b;
}

// 空间压缩
int profitableSchemes(int n, int minProfit, int *group, int groupSize, int *profit, int profitSize) {
    const int MOD = 1e9 + 7;
    int dp[n + 1][minProfit + 1];
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= minProfit; ++j)
            dp[i][j] = 0;
    // 从最上一层，i == groupSize越界的时候开始填
    for (int r = 0; r <= n; ++r) dp[r][0] = 1;
    for (int i = groupSize - 1; i >= 0; i--) {
        // dp没更新前代表上一层二维表
        for (int r = n; r >= 0; r--) {
            for (int s = minProfit; s >= 0; s--) {
                int p1 = dp[r][s];
                int p2 = group[i] <= r ? dp[r - group[i]][max(s - profit[i], 0)] : 0;
                dp[r][s] = (p1 + p2) % MOD;
            }
        }
    }
    return dp[n][minProfit];
}

688. 骑士在棋盘上的概率

double ***dp;

// 从(i, j)出发，还剩k步要走
double recursive(int n, int i, int j, int k) {
    // 越界
    if (i < 0 || i >= n || j < 0 || j >= n) return 0;
    if (dp[i][j][k] != -1) return dp[i][j][k];
    double res = 0;
    if (k == 0) {
        // 仍在棋盘上
        res = 1;
    } else {
        // 八个位置，每个位置概率八分之一
        res += (recursive(n, i - 2, j + 1, k - 1) / 8);
        res += (recursive(n, i - 1, j + 2, k - 1) / 8);
        res += (recursive(n, i + 1, j + 2, k - 1) / 8);
        res += (recursive(n, i + 2, j + 1, k - 1) / 8);
        res += (recursive(n, i + 2, j - 1, k - 1) / 8);
        res += (recursive(n, i + 1, j - 2, k - 1) / 8);
        res += (recursive(n, i - 1, j - 2, k - 1) / 8);
        res += (recursive(n, i - 2, j - 1, k - 1) / 8);
    }
    dp[i][j][k] = res;
    return res;
}

// 记忆化搜索
double knightProbability(int n, int k, int row, int column) {
    dp = (double ***) malloc(sizeof(double **) * n);
    for (int i = 0; i < n; ++i)
        dp[i] = (double **) malloc(sizeof(double *) * n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = (double *) malloc(sizeof(double) * (k + 1));
            for (int l = 0; l < k + 1; ++l) {
                dp[i][j][l] = -1;
            }
        }
    }
    return recursive(n, row, column, k);
}

2435. 矩阵中和能被 K 整除的路径

const int MOD = 1e9 + 7;
int rowSize;
int columnSize;

// 从(i, j)出发，走到右下角，有多少条路径的累加和模k的余数是0
// 如果dp的第三维度是sum，那么数组大小不确定，而且从前面到当前位置的sum可能性很多
long long recursive(int **grid, int i, int j, int k, int sum) {
    // 越界
    if (i >= rowSize || j >= columnSize) return 0;
    // 累加当前格子
    sum += grid[i][j];
    // 到终点，且能被整除
    if (i == rowSize - 1 && j == columnSize - 1 && (sum % k == 0)) {
        return 1;
    }
    // 往下往右
    return (recursive(grid, i + 1, j, k, sum) + recursive(grid, i, j + 1, k, sum)) % MOD;
}

// 暴力超时
int numberOfPaths(int **grid, int gridSize, int *gridColSize, int k) {
    rowSize = gridSize;
    columnSize = *gridColSize;
    return recursive(grid, 0, 0, k, 0);
}

const int MOD = 1e9 + 7;
int rowSize;
int columnSize;
int ***dp;

// 从(i, j)出发，走到右下角，有多少条路径的累加和模k的余数是r
// 如果dp的第三维度是r，那么数组大小确定是k
long long recursive(int **grid, int i, int j, int k, int r) {
    // 越界
    if (i >= rowSize || j >= columnSize) return 0;
    // 到终点，且能被整除
    if (i == rowSize - 1 && j == columnSize - 1 && (grid[i][j] % k == r)) {
        return 1;
    }
    // 后面要凑出来的余数
    int need = (r - (grid[i][j] % k) + k) % k;
    return (recursive(grid, i + 1, j, k, need) + recursive(grid, i, j + 1, k, need)) % MOD;
}

// 暴力超时
int numberOfPaths(int **grid, int gridSize, int *gridColSize, int k) {
    rowSize = gridSize;
    columnSize = *gridColSize;
    return recursive(grid, 0, 0, k, 0);
}

const int MOD = 1e9 + 7;
int rowSize;
int columnSize;
int ***dp;

// 从(i, j)出发，走到右下角，有多少条路径的累加和模k的余数是r
long long recursive(int **grid, int i, int j, int k, int r) {
    // 越界
    if (i >= rowSize || j >= columnSize) return 0;
    // 到终点，且能凑出需要的余数
    if (i == rowSize - 1 && j == columnSize - 1 && (grid[i][j] % k == r)) return 1;
    if (dp[i][j][r] != -1) return dp[i][j][r];
    // 后面要凑出来的余数
    int need = (r - (grid[i][j] % k) + k) % k;
    int res = (recursive(grid, i + 1, j, k, need) + recursive(grid, i, j + 1, k, need)) % MOD;
    dp[i][j][r] = res;
    return res;
}

// 记忆化搜索
int numberOfPaths(int **grid, int gridSize, int *gridColSize, int k) {
    rowSize = gridSize;
    columnSize = *gridColSize;
    // 记录当前坐标，和到到当前位置的r
    dp = (int ***) malloc(sizeof(int **) * rowSize);
    for (int i = 0; i < rowSize; ++i)
        dp[i] = (int **) malloc(sizeof(int *) * columnSize);
    for (int i = 0; i < rowSize; ++i) {
        for (int j = 0; j < columnSize; ++j) {
            dp[i][j] = (int *) malloc(sizeof(int) * k);
            memset(dp[i][j], -1, sizeof(int) * k);
        }
    }
    return recursive(grid, 0, 0, k, 0);
}

const int MOD = 1e9 + 7;
int rowSize;
int columnSize;

int numberOfPaths(int **grid, int gridSize, int *gridColSize, int k) {
    rowSize = gridSize;
    columnSize = *gridColSize;
    // 看成二维表，表中每个元素有k层
    int dp[rowSize][columnSize][k];
    // 静态数组的所有元素都是连续分配
    memset(dp, 0, sizeof(int) * rowSize * columnSize * k);
    // 到终点，且能凑出需要的余数，其他位置都已初始化为0
    dp[rowSize - 1][columnSize - 1][grid[rowSize - 1][columnSize - 1] % k] = 1;

    // 每个格子只依赖于右边和下边的格子
    // 从下往上推最后一列
    for (int i = rowSize - 2; i >= 0; i--)
        for (int r = 0; r < k; ++r)
            dp[i][columnSize - 1][r] = dp[i + 1][columnSize - 1][(k + r - grid[i][columnSize - 1] % k) % k];
    // 从右往左推最后一行
    for (int j = columnSize - 2; j >= 0; j--)
        for (int r = 0; r < k; ++r)
            dp[rowSize - 1][j][r] = dp[rowSize - 1][j + 1][(k + r - grid[rowSize - 1][j] % k) % k];

    for (int i = rowSize - 2; i >= 0; i--) {
        for (int j = columnSize - 2; j >= 0; j--) {
            for (int r = 0; r < k; ++r) {
                int need = (k + r - grid[i][j] % k) % k;
                dp[i][j][r] = (dp[i + 1][j][need] + dp[i][j + 1][need]) % MOD;
            }
        }
    }
    return dp[0][0][0];
}

87. 扰乱字符串

// 返回s1[l1...r1]和s2[l2...r2]是否是扰乱串
bool recursive(char *s1, char *s2, int l1, int r1, int l2, int r2) {
    // 每次比较的都是等长的字符串

    // 都只有一个字符时
    if (l1 == r1) return s1[l1] == s2[l2];

    // 左右两部分等长
    // s1[l1...i][i+1...r1]
    // s2[l2...j][j+2...r2]
    for (int i = l1, j = l2; i < r1; i++, j++)
        if (recursive(s1, s2, l1, i, l2, j) && recursive(s1, s2, i + 1, r1, j + 1, r2))
            return true;

    // s1左等于s2右
    // s1[l1...i][i+1...r1]
    // s2[l2...j-1][j...r2]
    for (int i = l1, j = r2; i < r1; i++, j--)
        if (recursive(s1, s2, l1, i, j, r2) && recursive(s1, s2, i + 1, r1, l2, j - 1))
            return true;
    return false;
}

// 暴力超时
bool isScramble(char *s1, char *s2) {
    return recursive(s1, s2, 0, strlen(s1) - 1, 0, strlen(s2) - 1);
}

// 返回s1从l1开始和s2从l2开始长度为len的字符串是否是扰乱串
bool recursive(char *s1, char *s2, int l1, int l2, int len) {
    // 每次比较的都是等长的字符串

    // 都只有一个字符时
    if (len == 1) return s1[l1] == s2[l2];

    // 左右两部分等长，左k右len-k
    // s1[l1...i][i+1...r1]
    // s2[l2...j][j+2...r2]
    for (int k = 1; k < len; ++k)
        if (recursive(s1, s2, l1, l2, k) && recursive(s1, s2, l1 + k, l2 + k, len - k))
            return true;

    // s1左等于s2右
    // s1[l1...i][i+1...r1]
    // s2[l2...j-1][j...r2]
    for (int i = l1 + 1, j = l2 + len - 1, k = 1; k < len; i++, j--, k++)
        if (recursive(s1, s2, l1, j, k) && recursive(s1, s2, i, l2, len - k))
            return true;
    return false;
}

// 暴力超时，减少了一个参数
bool isScramble(char *s1, char *s2) {
    return recursive(s1, s2, 0, 0, strlen(s1));
}


int ***dp;

// 返回s1从l1开始和s2从l2开始长度为len的字符串是否是扰乱串
bool recursive(char *s1, char *s2, int l1, int l2, int len) {
    // 都只有一个字符时
    if (len == 1) return s1[l1] == s2[l2];

    if (dp[l1][l2][len] != 0) return dp[l1][l2][len] == 1;

    bool res = false;
    // 左右两部分等长，左k右len-k
    // s1[l1...i][i+1...r1]
    // s2[l2...j][j+2...r2]
    for (int k = 1; k < len; ++k)
        if (recursive(s1, s2, l1, l2, k) && recursive(s1, s2, l1 + k, l2 + k, len - k)) {
            res = true;
            break;
        }

    // s1左等于s2右
    // s1[l1...i][i+1...r1]
    // s2[l2...j-1][j...r2]
    if (!res) {
        for (int i = l1 + 1, j = l2 + len - 1, k = 1; k < len; i++, j--, k++)
            if (recursive(s1, s2, l1, j, k) && recursive(s1, s2, i, l2, len - k)) {
                res = true;
                break;
            }
    }
    dp[l1][l2][len] = res ? 1 : -1;
    return res;
}

// 记忆化搜索
bool isScramble(char *s1, char *s2) {
    int length = strlen(s1);
    // 0：未处理；-1：返回false；1：返回true
    dp = (int ***) malloc(sizeof(int **) * length);
    for (int i = 0; i < length; ++i)
        dp[i] = (int **) malloc(sizeof(int *) * length);
    for (int i = 0; i < length; ++i) {
        for (int j = 0; j < length; ++j) {
            dp[i][j] = (int *) malloc(sizeof(int) * (length + 1));
            memset(dp[i][j], 0, sizeof(int) * (length + 1));
        }
    }
    return recursive(s1, s2, 0, 0, length);
}

// 自下而上
bool isScramble(char *s1, char *s2) {
    int length = strlen(s1);
    // 0：未处理；-1：返回false；1：返回true
    bool dp[length][length][length + 1];
    memset(dp, 0, sizeof(bool) * length * length * (length + 1));
    // len=1
    for (int l1 = 0; l1 < length; ++l1)
        for (int l2 = 0; l2 < length; ++l2)
            dp[l1][l2][1] = s1[l1] == s2[l2];
    for (int len = 2; len <= length; ++len) {
        for (int l1 = 0; l1 <= length - len; ++l1) {
            for (int l2 = 0; l2 <= length - len; ++l2) {
                for (int k = 1; k < len; ++k) {
                    if (dp[l1][l2][k] && dp[l1 + k][l2 + k][len - k]) {
                        dp[l1][l2][len] = true;
                        break;
                    }
                }
                if (!dp[l1][l2][len]) {
                    for (int i = l1 + 1, j = l2 + len - 1, k = 1; k < len; i++, j--, k++) {
                        if (dp[l1][j][k] && dp[i][l2][len - k]) {
                            dp[l1][l2][len] = true;
                            break;
                        }
                    }
                }
            }
        }
    }
    return dp[0][0][length];
}

标签：return,recursive,int,s2,s1,三维,动态,规划,dp
From： https://www.cnblogs.com/sprinining/p/18001443

相关文章

  • 01 分数规划
    有\(n\)个01变量\(x_1\simx_n\)，同时有\(a_1\sima_n,b_1\simb_n\).同时有约束条件：用集合\(S\)表示，这个\(S\)中每一个元素表示一个\(x_1\simx_n\)的取法。（平时见到的题不咋有约束）我们要给\(x_1\simx_n\)赋值，使得\(\dfrac{\sumx_ia_i}{\sumx_ib_i}\)最大，还要......
  • 动态规划 背包问题
    01背包 二维//二维#include<iostream>#include<cmath>usingnamespacestd;constintN=1010;intp[N][N]={0};intv[N];intw[N];intm,n;intmain(){cin>>n>>m;for(inti=1;i<=n;i++){cin>>v[i]>>w[i];......
  • 动态树直径小记
    本文采用BY-NC-SA协议发布。要求：给你一棵树，边带权，每次断边连边（保证合法且仍是树），在线求每次修改后的直径。LCT（咕）TopTree拆边，然后用negiizhao论文里的方法维护。实现时注意，翻转标记会影响合并的信息，要swap一下。#include<iostream>#include<unordered_map>#includ......
  • Vue 搭配GSAP实现颜色动态渐变
    重点使用reactive构造响应式的对象存储颜色，使用gsap.to操作响应式对象实现颜色渐变代码lettoTimeLine:TweenletoverTimeLine:TweentypeColor={value:string}typeTween=gsap.core.TweenconstaddItemColor=reactive<C......
  • 02 三维世界与模型
    了解三维世界物体的位置是使用某个坐标轴下的坐标（x，y，z）进行描述。 坐标系分为两种：左手坐标系、右手坐标系。z轴坐标系是这两种坐标系的区别点。OpenGL使用的是右手坐标系。OpenGL做了什么？先确定坐标系（原点、x,y,z得指向），再确定摄像机（观察者）的位置和方向。这样就能渲染出图......
  • 【京东云新品发布月刊】2024年1月产品动态来啦
     1）【莫奈可视化平台】新品上线京东莫奈可视化平台通过自由拖拽、图形化编辑、所见即所得的方式，快速实现极致酷炫、直观清晰的视觉场景，将海量繁杂数据背后所蕴含的价值更直观、深层、全面的展现出来，辅助决策者合理决策。2）【移动端应用监控SGM-mobile】新品上线移动端监控S......
  • [职场] 职业规划的重要性有些什么
    职业规划是一个非常重要的过程，它可以帮助个人更好地把握自己的职业方向，确定自己的最佳职业道路，提高个人素质和社会竞争力，实现个人职业成功和满足个人职业需求。一.重要性1.提升职业满意度当一个人有明确的职业目标和发展计划时，就会感到自己对未来的把控，进而提高职业满意度，相比之下，......
  • element实现大图预览和图片动态加载
    element的el-image组件支持大图预览模式，但需要和小图模式配合使用，项目中刚好有需求需要直接使用大图预览并且需要支持图片的动态加载，研究了一下el-image组件的源码发现el-image组件是通过引用image-viewer组件实现的大图预览的，刚好可以利用一下！image-viewer属性urlList:图......
  • Python下的三维建模和可视化
    本文介绍基于AnyCADRapidPy三维图形平台开发Python的三维应用1准备工作1.1安装vc_resit2022在Windows下，AnyCADRapidSDK依赖VistualC++运行时库，64位版本需要在客户机上安装vc_redist.x64.exe微软官方下载地址：x64:vc_redist.x64.exe1.2安装Python3.12:::w......
  • 动态 DP 学习笔记
    动态DPP4719动态DP给定一棵\(n\)(\(n\leqslant10^5\))个点的树，点带点权。有\(m\)(\(m\leqslant10^5\))次操作，每次操作给定\(x,y\)，表示修改点\(x\)的权值为\(y\)。你需要在每次操作之后求出这棵树的最大权独立集的权值大小。首先考虑\(m=0\)时的做法，可以......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99