openjudge补习

  • 8758 2的幂次方表示

    印象中什么时候好像调了好久的样子,其实就是直接递归的做就好了

  • 整数划分

    1
    2
    3
    4
    5
    dp[0][0] = 1;
    g(i, 1, n) {
    g(j, 1, i) dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];
    }
    // dp[i][j] 是i分成j份的方案数
  • zipper

    问A和B两个串 能否交叉组合成C,要求AB内部相对顺序不变

    dp[i][j] 表示A[1..i]B[1..j] 能否拼成C[1..i+j] 转移就判一下最后一个字符是否匹配

  • 复杂的整数划分问题

第一行: N划分成K个正整数之和的划分数目
第二行: N划分成若干个不同正整数之和的划分数目
第三行: N划分成若干个奇正整数之和的划分数目

ref: https://blog.csdn.net/tp7309/article/details/54880495

n划分成可相同的正整数

dp[i][j] 表示把i分成不超过j的数的和
dp[i][j] = dp[i][j - 1] + dp[i - j][j]
要么每个数都小于j,要么至少有一个等于j,把那个j去掉。

i < jdp[i][j] = 0

边界:dp[0][0] = 1;

不相同

dp[i][j] = dp[i][j - 1] + dp[i - j][j - 1]
要么每个数都小于j,要么有一个数等于j,把唯一的那个j去掉,剩下的数都小于j了。

k个数

dp[i][j] 表示把i分成j份
dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1]
要么给之前的j组每个数加一,要么取出来一个1单独装一组

i < jdp[i][j] = dp[i][i]

边界:dp[0][i] = 1;

分成奇数

f[i][j] 表示i分成j个正奇数
g[i][j] 分成正偶数

g[i][j] = f[i - j][j]
偶数来自每一组奇数加一
f[i][j] = f[i - 1][j - 1] + g[i - j][j]
奇数来自偶数加一,或者最后一个1单独一组
边界:f[0][0] = g[0][0] = 1

  • 6047:切蛋糕

    dp[i][j[k]表示i*j大小的切k块的答案(最大块面积的最小值)

    转移的时候就枚举横竖的切法就可以了

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    g(i, 1, 20) {
    g(j, 1, 20) {
    dp[i][j][1] = i * j;
    g(k, 2, 20) {
    dp[i][j][k] = oo;
    f(r, 1, i) {
    f(p, 1, k) {
    dp[i][j][k] = std::min(dp[i][j][k], std::max(dp[r][j][p], dp[i - r][j][k - p]));
    }
    }
    f(c, 1, j) {
    f(p, 1, k) {
    dp[i][j][k] = std::min(dp[i][j][k], std::max(dp[i][c][p], dp[i][j - c][k - p]));
    }
    }
    }
    }
    }

感觉比之前菜多了…… 重开几页补补题吧QAQ