1 条题解

  • 1
    @ 2025-3-5 22:27:46

    n8n \leq 8

    暴力枚举每个骰子选或不选即可。

    n50n \leq 50

    我们考虑一个 dp。

    我们设 fi,j,kf_{i,j,k} 表示前 ii 个骰子选了 jj 个且和为 kk 的方案数。

    转移只要枚举这一个骰子是啥就好了。

    复杂度 O(n4)O(n^4)

    n200n \leq 200

    不难注意到转移的是一段区间,我们使用前缀和优化 dp 即可做到 O(n3)O(n^3)

    然后我们注意到此时空间不太够用的样子,我们使用滚动数组并将一些值开成 int 即可通过这个题。


    一点也不卡常。

    信息

    ID
    1331
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    5
    已通过
    3
    上传者