(10067) 수열 나누기

https://www.acmicpc.net/problem/10067

단계별로 풀어보기

62단계(동적 계획법 최적화 1) 4번째

 

 

 

dp[x][y]를 y번째 원소까지 x번 나눴을 때 최대 점수라고 하면

dp[x][y]= max(dp[x-1][i]+S[i]*(S[y]-S[i]))이다. 따라서 x=0부터 시작해 컨벡스 헐 DP를 k번 돌리면 된다.

이 문제는 역추적도 요구하고 있으므로 선분의 정보를 나타내는 구조체에 선분의 원래 인덱스를 나타내는 int 자료형 인자를 추가하고, DP를 갱신할 때 prev 배열에 선분을 기록해 최대값을 구한 뒤 prev 배열을 거슬러 올라가면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
typedef pair<pair<long,long>,pair<double,int>> LF_t; // Linear Function ax+b(x>=c)(index d)

inline double cross(LF_t f1, LF_t f2){
  if(f1.first.first==f2.first.first)  return 0.0;
  return static_cast<double>(f2.first.second-f1.first.second)/(f1.first.first-f2.first.first);
}

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, k;
  
  cin >> n >> k;
  
  vector<long> x(n+1), s(n+1);
  vector dp(2, vector<long> (n+1));
  vector prev(k+1, vector<int> (n+1));
  vector<LF_t> f;
  
  for(int i=1;i<=n;i++){
    cin >> x[i];
    s[i]= s[i-1]+x[i];
  }
  
  for(int i=1;i<=k;i++){
    f.clear();
    
    for(int j=i+1,fpos=0;j<=n-k+i;j++){
      LF_t now= {{s[j-1], dp[0][j-1]-s[j-1]*s[j-1]}, {0.0f, j-1}};
      
      while(!f.empty()){
        now.second.first= cross(f.back(), now);

        if(f.back().first.first!=now.first.first && f.back().second.first<now.second.first){
          break;
        }
        
        f.pop_back();
        fpos= min<int>(fpos, f.size()-1);
      }
      
      f.push_back(now);
      
      while(fpos+1<f.size() && f[fpos+1].second.first<s[j]) fpos++;
      
      dp[1][j]= s[j] * f[fpos].first.first + f[fpos].first.second;
      prev[i][j]= f[fpos].second.second;
    }
    
    dp[0]= dp[1];
    dp[1]= vector<long> (n+1);
  }
  
  cout << dp[0][n] << "\n";
  
  for(int i=k,x=prev[k][n];i>0;i--){
    cout << x << " ";
    x= prev[i-1][x];
  }
  
  return 0;
}