1 条题解

  • 1
    @ 2021-8-7 18:16:50

    出题人:一只书虫仔 Data:w33z 验题人:MatKave&w33z&一只书虫仔

    Description

    给定一个 nn 行的不规则矩阵,第 ii 行的长度为 aia_i

    现在在上面放 kk 个棋子,要保证没有两个棋子在同一行或同一列。

    求有多少个放置方案。

    1n,k1031 \le n,k \le 10^31ai1051 \le a_i \le 10^5

    Solution

    Subtask 1:我会循环把 aia_i 加起来!

    Subtask 2:我会暴力!

    Subtask 3:考虑 dp,定义 dpi,kdp_{i,k} 为放置到第 ii 行时第 1i1 \sim i 行一共放了 kk 个棋子的方案数,分类讨论:

    • 这一行不放,可以直接从上一行转移过来,dpi,k=dpi1,kdp_{i,k}=dp_{i-1,k}
    • 这一行放,能放的位置个数即为这一行的长度减去已经放了的棋子个数,即从上一行转移过来的时候乘上能放的位置个数即可,dpi,k=dpi1,k1×(ai(k1))dp_{i,k}=dp_{i-1,k-1} \times (a_i-(k-1))

    把这两部分加起来即可。

    Subtask 4:如果不会考虑 Subtask 3 的“这一行放”的情况的话,这一个 Subtask 可以拯救你。

    正解:继续考虑 Subtask 3,如果适用于所有情况,我们有一个问题,如果上一行比这一行要长,有可能上一行放了一些棋子在第 pp 列,然而这一行没有 pp 个格子那么多。这个问题很好解决,在一开始放的时候从最短的那一行开始放,然后一直放到最长的那一行即可,代码实现的时候排一下序即可。

    O(nk)\mathcal O(nk)

    评价:中规中矩的签到题 * 2,给良心的出题人点赞!

    • 1

    信息

    ID
    176
    时间
    1000ms
    内存
    128MiB
    难度
    8
    标签
    递交数
    38
    已通过
    8
    上传者