AGC041D-Problem Scores 题解

题目链接

luogu
atcoder

分析

令 \(k=\left \lfloor \frac{n}{2} \right \rfloor\)
对于第三个条件,只需要满足 \(\sum_{i=1}^{k+1}a[i]<\sum_{i=n-k+1}^{n}a[i]\) 即可
有一个 \(trick\)： 构造一个单调不降或不增的序列 可以转化为每次做一次前缀加操作
例如本题要求构造一个单调不降的序列，且满足每个值都在 \([1,n]\) 中
可以转化为：先将每个数初始化为 \(n\) 每次找一个前缀 \(-1\) 进行不超过 \(n-1\) 次
我们发现每次操作对于 \(\sum_{i=1}^{k+1}a[i]-\sum_{i=n-k+1}^{n}a[i]\) 的贡献是不变的,可以 \(O(n)\) 预处理
最初差值为 \(n\) ,每次操作的贡献一定小于 \(0\) ,要保证最终差值不低于 \(1\) 则最多进行 \(n-1\) 次操作
也就是说，只要保证差值 \(>0\) 即可满足题中所有条件
之后就不难 \(DP\) 了
记 \(f[i][j]\) 为选择前 \(i\) 个操作，差值为 \(j\) 的方案数
则 \(f[n]=1\)
\(f[i][j]=f[i-1][j-k*w[i]]\)
利用完全背包的思想即可做到 \(O(n^2)\)

本来想的是 \(1\)~\(k\) , \(n\)~\(n-k+1\) 分别 \(DP\) 然后将两次 \(DP\) 的结果合到一起，但要记的状态太多，就寄了

代码

#include<bits/stdc++.h>
using namespace std;

const int N=6005;

int w[N],f[N];

int main(){
	int n,m;
	scanf("%d %d", &n, &m);
	int k=n/2;
	
	for(int i=1;i<=n;i++){//计算每次操作的贡献 
		w[i]=w[i-1];
		if(i<=k+1) w[i]--;
		if(i>=n-k+1) w[i]++;
	}
	
	f[n]=1;
	for(int i=1;i<=n;i++)
		for(int j=n+w[i];j>=0;j--)//由于 w[i]<0 所以 j 倒序枚举 
			f[j]=(f[j]+f[j-w[i]])%m;
	int ans=0;
	for(int i=1;i<=n;i++) ans=(ans+f[i])%m;
	printf("%d\n", ans);
	return 0;
}