1 条题解

  • 37
    @ 2022-3-3 14:59:52
    本题属于计数型动态规划问题,我们可以定义出状态dp[i][j]表示1~i的数字拆分成两个子数组求和的差的绝对值为j的方案数。
    方程为 dp[i][j] = dp[i-1][j+i] + dp[i-1][abs(j-i)]
    答案需要特判m == 0时的情况,例如n=3, m=0时,只有一组A1={1, 2}, A2={3},但使用dp会将正反计算两次,因此需要对结果除以2;
    其他情况下,不会出现正反计算两次的情况,因此直接输出即可。
    
    
    • 1

    信息

    ID
    178
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    1493
    已通过
    279
    上传者