2 条题解

  • 4
    @ 2021-8-27 18:21:47

    在我的个人博客中阅读

    题面

    题意

    给出一个长度为 nn 的序列 SSSS 单调递增,问你有多少个序列 TT 以满足下列条件:

    1. TTSS 的一个排列。
    2. i=1nmin(Si, Ti)=k\sum_{i=1}^{n} \min(S_i,~T_i) = k

    1k2500, 1n50, 1Si501 \le k \le 2500,~1 \le n \le 50,~1 \le S_i \le 50

    分析

    我们发现 kk 的值非常小,所以我们考虑使用类似背包的方法考虑每一个 SiS_iTiT_i 对总答案的贡献。

    由于 SS 单调递增所以 SS 中的数互不相同,因此我们可以直接考虑分类讨论值 SiS_iTT 中的位置,令 Tj=SiT_j = S_i 则:

    1. j<ij < iSj<Si=TjS_j < S_i = T_j,因此 SiS_i 对答案产生 00 的贡献。
    2. j=ij = iSj=Si=TjS_j = S_i = T_j,因此 SiS_i 对答案产生 SiS_i 的贡献。
    3. j>ij > iSj>Si=TjS_j > S_i = T_j,因此 SiS_i 对答案产生 SiS_i 的贡献。

    计算答案的问题解决了,但是如何记录 SiS_iTT 中的位置?显然我们只关心 jjii 的大小关系,并不关心 jj 的具体值。因此我们只需要知道有多少中情况满足 j<ij < ij=ij = ij>ij > i 即可。

    考虑使用 DP 解决此问题,f[i][j][k]f[i][j][k] 表示已考虑 S1SiS_1 \sim S_i 部分,T1TiT_1 \sim T_i 中有 jj 个位置尚未确定值,且 S1SiS_1 \sim S_i 部分对总答案的贡献为 kk 的方案数。转移时枚举 jjii 的大小关系和 TiT_i 是否确定值即可。TiT_i 不确定值时即意味 TiT_i 将用 >Si> S_i 的数填充,TiT_i 确定值时即意味 TiT_i 将用 Si\le S_i 的数填充。

    具体转移见代码,建议手画几个图细心分析。

    代码

    View on GitHub

    • 4
      @ 2021-8-27 17:41:27

      在我的个人博客中阅读

      50 分:

      暴力枚举即可

      100 分:

      设输入的序列为 aia_i。容易发现,如果我们按原序列从左往右扫,扫到第 ii 个位置时,我们要考虑的是这一个位置要填什么以及 aia_i 要填到哪个位置上。

      并且一共只有 5 种情况:

      • aia_i 填到 ii 上;
      • 拿一个比 aia_i 小的数填到 ii 上并且 aia_i 填到比 ii 小的位置上;
      • 拿一个比 aia_i 小的数填到 ii 上并且 aia_i 填到比 ii 大的位置上;
      • 拿一个比 aia_i 大的数填到 ii 上并且 aia_i 填到比 ii 大的位置上;
      • 拿一个比 aia_i 大的数填到 ii 上并且 aia_i 填到比 ii 小的位置上

      那么我们记 fi,j,pf_{i,j,p} 表示现在填完第 ii 个数,比 ii 小(包括 ii)的有 jj 个没填,并且算出来的价值为 pp 的方案数。假设我们现在考虑 i+1i+1 位填的数,分别考虑以上的五种情况。不过这里要注意的一点就是当这个位置填的数比它小时,是无法确定究竟是 jj 个当中的哪一个,因此这一部分的价值需要在之前填上 jj 这一位的时候就统计在答案中。

      为了方便表述,借助标程的代码段进行解释(一些边界判断和取模略去):

      f[i+1][j][p+a[i+1]] += f[i][j][p];//第 i+1 位填 a[i+1],不会产生新的未填项,并且产生新贡献为 a[i+1]
      f[i+1][j-1][p] += f[i][j][p]*j*j;//第 i+1 位填比 a[i+1] 小的数并且 a[i+1] 填到比 i+1 小的位置上。减少一个未填项,产生新贡献为 0(这些贡献之前之前已经计算)
      f[i+1][j][p+a[i+1]] += f[i][j][p]*j;//第 i+1 位填比 a[i+1] 小的数并且 a[i+1] 填到比 i+1 大的位置上。未填项数目不改变,产生新贡献为 a[i+1](贡献来自 a[i+1] 填到的那位)
      f[i+1][j+1][p+2*a[i+1]] += f[i][j][p];//第 i+1 位填比 a[i+1] 大的数并且 a[i+1] 填到比 i+1 大的位置上。未填项数目 +1,产生新贡献为 2*a[i+1](贡献来自 i+1 位和 a[i+1] 填到的那位)
      f[i+1][j][p+a[i+1]] += f[i][j][p]*j;//第 i+1 位填比 a[i+1] 大的数并且 a[i+1] 填到比 i+1 小的位置上。未填项数目不改变,产生新贡献为 a[i+1](贡献来自 i+1 位)
      
      • 1

      信息

      ID
      189
      时间
      1000ms
      内存
      256MiB
      难度
      9
      标签
      递交数
      47
      已通过
      4
      上传者