[AGC041D] Problem Scores

Kubic · 2021-04-25 19:23:43 · 题解

这是一篇思想极度简洁的题解。

首先先考虑转化一下第三个条件。

令 k=\lfloor\dfrac{n}{2}\rfloor。

则我们可以发现满足条件三等价于前 k+1 个数之和严格大于后 k 个数。

此时再考虑如何刻画第二个条件。

初始时令 A_i=n，每一次选择一个前缀减去 1，这样所生成的序列一定不重不漏地覆盖了所有的满足条件二情况。

维护 \Delta= 前 k+1 个数之和 - 后 k 个数之和。

容易发现 \Delta 初值为 n。

对于每一个 i 容易预处理出 w_i 表示对前缀 A[1\dots i] 进行一次操作时 \Delta 会发生什么变化。显然无论对哪个前缀操作 \Delta 都会减少。

那么现在就转化为一个完全背包问题：

有 n 种物品，每一种都有无限个，第 i 种物品重量为 w_i，现在要选出一些物品使得总重不超过 n-1，求方案数。

容易使用 dp 在 O(n^2) 时间内计数。

简短的代码：

#include <bits/stdc++.h>
using namespace std;
#define N 5005
int n,P,ans,w[N],dp[N];
int main()
{
    scanf("%d %d",&n,&P);dp[n]=1;
    for(int i=1;i<=(n+1)/2;++i) w[i]=i;
    for(int i=1;i<=n/2;++i) w[n-i+1]=i;
    for(int i=1;i<=n;++i) for(int j=n;j>=w[i];--j)
        dp[j-w[i]]=(dp[j-w[i]]+dp[j])%P;
    for(int i=1;i<=n;++i) ans=(ans+dp[i])%P;
    printf("%d\n",ans);return 0;
}