Official

E - Work or Rest Editorial by physics0523


円環上で問題を解く際は、特別な意味のあるものを先頭に固定するのが定石です。そのようにすることで、末尾から先頭に繋がる場合の考察を最低限に済ませることができます。
今回は、「休日」(のうち \(1\) つ)を曜日 \(1\) に固定することがそれにあたるので、そこから始めましょう。

「休日」同士の間隔が \(d\) 日である部分において、間に挟まる「平日」の生産量の総和はいくつでしょうか? これは、以下のように記述できます。

  • \(d=0\) のとき \(0\)
  • \(d=1\) のとき \(A_1\)
  • \(d=2\) のとき \(2 \times A_1\)
  • \(d=3\) のとき \(2 \times A_1 + A_2\)
  • \(d=4\) のとき \(2 \times A_1 + 2 \times A_2\)
  • \(d=5\) のとき \(2 \times A_1 + 2 \times A_2 + A_3\)
  • \(\vdots\)

結局、 \(\displaystyle \sum_{i=1}^{d} A_{\lfloor \frac{i+1}{2} \rfloor}\) と表現することができます。これを \(B_d\) と定義します。

ここで、以下のような動的計画法を行います。
\(dp[\) 何曜日まで割り当てを決めたか \(][\) 現在連続している平日の数 \(] = \{\) 生産量の最大値 \(\}\)
遷移は以下の通りです。

  • \(dp[i][j]\)\(dp[i+1][j+1]\) に遷移
  • \(dp[i][j]+B_j\)\(dp[i+1][0]\) に遷移

\(dp[1][0]=0\) と初期化することで、冒頭で述べた「曜日 \(1\) を「休日」に固定する」が実現されます。
最終的な答えは以下のうち最大値です。
\(dp[N][i]+B_i (0 \le i \le N-1)\)
ここで \(B_i\) を足すことは、最後の「休日」から最初の「休日」( 曜日 \(1\) ) までの区間を考慮することに対応します。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<long long> a(n+1),b(n+1,0);
  for(int i=1;i<=n;i++){cin >> a[i];}
  for(int i=1;i<=n;i++){b[i]=b[i-1]+a[(i+1)/2];}
  vector<vector<long long>> dp(n+1,vector<long long>(n+1,-4e18));
  dp[1][0]=0;
  for(int i=1;i<n;i++){
    for(int j=0;j<=n;j++){
      if(dp[i][j]<0){continue;}
      dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);
      dp[i+1][0]=max(dp[i+1][0],dp[i][j]+b[j]);
    }
  }
  long long res=0;
  for(int i=0;i<n;i++){
    res=max(res,dp[n][i]+b[i]);
  }
  cout << res << "\n";
  return 0;
}

posted:
last update: