题解：P11500 [ROIR 2019 Day 2] 间歇训练

yi_hr · 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 思路

     设计状态：

5. f1[i][j]: 总负荷为 i，最后一天的负荷为 j，且前一天的负荷比倒数第二天的负荷小，即最后一次变化为增加。
6. 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;
       }