[JOI精進録] 難易度7「飴2」(JOI2021/2022 二次予選D)

問題リンク

atcoder.jp

問題概要

個の飴がある。この中からいくつか取り出したものの美味しさの総和の最大値を求めなさい。
ただし連続する個の中では2つまでしか選んではならない。

解説

AC解法(100/100点)

飴と飴を食べたうえで条件を満たす食べ方をしたときの美味しさの最大値
として更新をしていきます。ただし、は最大値の場所が一定とは限らないので累積maxを取って高速に最大値を取得する必要があります。

ACコード

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

int main(){
#define int long long
  int n,k,r(0); cin >> n >> k;
  vector dp(n,vector<int>(n+1)),res=dp,acc=dp;
  vector<int> A(n); for (int& a:A) cin >> a;
  dp[0][0] = A[0]; fill(acc[0].begin(),acc[0].end(),A[0]);
  for (int i(1);i < n;++i){
    dp[i][0] = A[i],acc[i][0] = A[i];
    for (int j(1);j <= i;++j) dp[i][j]=acc[j-1][max(i-k+1,0ll)]+A[i],acc[i][j]=max(acc[i][j-1],dp[i][j]),r=max(r,dp[i][j]);
    for (int j(i+1);j <= n;++j) acc[i][j]=acc[i][j-1];
  }
  cout << r << endl;
}

提出結果

atcoder.jp

ついでに

飴を食べて飴までの飴で条件を満たす選び方をしたときの最大値
と定義すると累積maxを取る必要がなくなり、定数倍高速化に繋がりました。

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

int main(){
#define int long long
  int n,k,r(0); cin >> n >> k;
  vector dp(n,vector<int>(n+1));
  vector<int> A(n); for (int& a:A) cin >> a;
  fill(dp[0].begin(),dp[0].end(),A[0]);
  for (int i(1);i < n;++i){
    dp[i][0] = A[i];
    for (int j(1);j <= i;++j) dp[i][j]=max(dp[i][j-1],dp[j-1][max(i-k+1,0ll)]+A[i]),r=max(r,dp[i][j]);
    for (int j(i+1);j <= n;++j) dp[i][j]=dp[i][j-1];
  }
  cout << r << endl;
}

atcoder.jp