[ABC285E] Work or Rest 题解

FFTotoro · 2023-01-16 18:48:01 · 题解

解法

解题之前，我们先定义一个数列 S，其中 S_i 代表若一周有 i+1 天且只有 1 个休息日（即 i 个工作日）时的工作效率。

由题目定义有：

若 i 为奇数，S_i=\left(2\sum\limits_{j=1}^{\left\lfloor i/2\right\rfloor}A_j\right)+A_{\left\lceil i/2\right\rceil}；

否则 S_i=2\sum\limits_{j=1}^{i/2}A_j。

令 F_i 为一周有 i 天时的最大工作效率，这个 F_i 的来源有两种情况：

• 一周有且仅有 1 个休息日：F_i=S_{i-1}；

• 一周不止 1 个休息日：令第一个休息日为周一，枚举第二个休息日，将整周划为两部分。然后我们就可以发现，若两个部分分别是 x 天和 y 天，根据 F 的定义，工作效率的最大值就为 F_{x+1}+F_{y+1}。更加形式化地说，如果一周不止一个休息日，那么有 F_i=\max\limits_{j=1}^{i-3} F_{j+1}+F_{i-1-j}。

两者取较大值即可。

最终答案即为 F_N。

如果你把上面的公式拿起来再细细回味，你就会发现它其实就是个完全背包。

放代码：

#include<bits/stdc++.h>
#define int long long // 记得 long long
using namespace std;
int a[5001],s[5001],f[5001];
main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<=n;i++)
    if(i&1)s[i]=s[i-1]+a[(i>>1)+1];
    else for(int j=1;j<=i>>1;j++)s[i]+=a[j]<<1; // 推导 S 数组
  for(int i=2;i<=n;i++){
    f[i]=s[i-1]; // 第一种情况
    for(int j=1;j<i-2;j++) // 第二种情况，枚举
      f[i]=max(f[i],f[j+1]+f[i-j-1]); // 转移，取较大值
  }
  cout<<f[n]<<endl; // 答案输出
  return 0;
}

后记

还记得去年的时候，我身边的同学都被简单的背包类动态规划搞得晕头转向，大家做背包基本都是运用“背模板”的方法。我那时常常对同学们说：“背什么模板啊，我一般都考场上手推的！”他们总是惊叹不已。

这次 ABC 中，E 题是个很不明显的背包。然而我的手推能力就在这里体现出来了，我花了 20 分钟，在草稿纸上写写画画。等到同学们发现了题目是个背包 DP 再提交时，发现我早已 AC——谁说“手推”就一定输“背模板”？

一时对模板的熟悉固然好，但是对算法“不透彻”的了解，在长远上看，是十分致命的。