自动搬运

查看原文

来自洛谷，原作者为

	yi_hr mamihlapinatapai

搬运于2025-08-24 23:07:53，当前版本为作者最后更新于2025-01-04 14:30:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

DP

题目重点，需要满足的条件：

1. 总负荷为 $n$。
2. 第一天的负荷为 $k$。
3. 相邻两天的负荷不同，即 $a_i \neq a_{i+1}$。
4. 负荷的增加和减少交替进行：
   • 如果 $a_i < a_{i+1}$，则 $a_{i+1} > a_{i+2}$。
   • 如果 $a_i > a_{i+1}$，则 $a_{i+1} < a_{i+2}$。

DP 思路

设计状态：

1. f1[i][j]: 总负荷为 $i$，最后一天的负荷为 $j$，且前一天的负荷比倒数第二天的负荷小，即最后一次变化为增加。
2. f2[i][j]： 总负荷为 $i$，最后一天的负荷为 $j$，且前一天的负荷比倒数第二天的负荷大，即最后一次变化为减少。

递推边界：

• 第一天的负荷为 $k$。
• 对于第二天的负荷 $a_2$：
  • 若 $a_2>k$，则将 f1[k + a2][a2]赋值。
  • 若 $a_2<k$，则将 f1[k + a2][a2]赋值。
• 如果 $k = n$，则序列 k 是唯一的有效序列。

状态转移：

对于每一个总负荷 $s$ 从 $k+1$ 到 $n$：

1. 计算前/后缀和：
   • s1[v]：表示所有 $v'<v$ 的 f2[s][v'] 的累加和。
   • s2[v]：表示所有 $v'>v`$ 的 f1[s][v'] 的累加和。
2. 转移状态：
   • 对于每下一个可能的负荷 $u$：
     • f2：将所有上一次是 f1[s][v'] 且 $v' > u$ 的情况累加到 f2[s + u][u]。
     • f1：将所有上一次是 f2[s][v'] 且 $v' < u$ 的情况累加到 f1[s + u][u]。

答案

答案为 f1[n][v] 和 f2[n][v] 对所有 $v$ 的和。如果 $k = n$，还需要加上序列 k。

code

注： 个人习惯，用一维数组模拟二维数组，见谅。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=1e9+7,N=5e7+9,M=1e5+9;
int n,k;
int f1[N],f2[N];
int s1[M],s2[M];
ll ans;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(int i=k+1;i<=n;i++){
		if(k+i<=n) {
			f1[(k+i)*(n+1)+i]=(f1[(k+i)*(n+1)+i]+1)%MOD;
		}
	}
	for(int i=1;i<k;i++){
		if(k+i<=n){
			f2[(k+i)*(n+1)+i]=(f2[(k+i)*(n+1)+i]+1)%MOD;
		}
	}
	if(k==n){
		ans=1;
	}
	for(int i=k+1;i<=n-1;i++){
		s1[0]=0;
		for(int j=1;j<=n;j++){
			s1[j]=(s1[j-1]+f2[i*(n+1)+j])%MOD;
		}
		s2[n +1] =0;
		for(int j=n;j>=1;j--){
			s2[j]=(s2[j+1]+f1[i*(n +1) +j]) % MOD;
		}
		for(int j=1;j<=n;j++){
			if(i+j>n) {
				continue;
			}
			ll cnt=s2[j+1];
			if(cnt){
				int idx=(i+j)*(n+1)+j;
				f2[idx]=(f2[idx]+cnt)%MOD;
			}
			ll cnt1=s1[j-1];
			if(cnt1){
				int idx=(i+j)*(n+1)+j;
				f1[idx]=(f1[idx]+cnt1)%MOD;
			}
		}
	}
	for(int j=1;j<=n;j++){
		ans=(ans+f1[n*(n+1)+j])%MOD;
		ans=(ans+f2[n*(n+1)+j])%MOD;
	}
	cout<<ans;
}