KUPC2015 D 高橋君の旅行

問題

D: 高橋君の旅行 - 京都大学プログラミングコンテスト2015 | AtCoder

問題概要

N日間の旅行を考える。
行える行動は今いる街iに滞在して所持金をB[i]変化するか、次の街i+1に移動して所持金をA[i]変化させる。
また、行動を行った直後の所持金が負の値になるように動くことは出来ない。
初日の所持金が0の時、N日後の所持金は最大でいくらになるか。

部分点解法

満点解法

解法

部分点解法は、dp[i][j] := i日目に街jにいる時の所持金の最大値、というDPを更新していけばよい。
満点解法は、N+1日目に街kにいるのが最適解だと仮定する。街kで旅を終えるときに、N-(街kに行くまでにかかる最短の日数)回、1~kの街のどこかに滞在することができる。この余分の滞在回数は1~kの中で一番Bの値が高い街に泊まればお金を最大化できる。
街kに行くまでにかかる最短の日数はシミュレーションを前計算でO(N)、参照でO(1)なので、あとはkを1~N+1まで試せば全体としてO(N)で答えを求めることができる。

コード

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>
 
#define INF 100000000
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
 
using namespace std;
 
#define MAX_N 100005
 
int N;
LL A[MAX_N];
LL B[MAX_N];
 
typedef pair<int, LL> iLL;
 
iLL PRE_DP[MAX_N];
 
int main(){
 
  cin >> N;
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  for (int i = 0; i < N; i++){
    cin >> B[i];
  }
 
  //PRE_DPの計算(前計算)
  for (int i = 0; i < MAX_N; i++){
    PRE_DP[i] = iLL(-1, -1);
  }
  PRE_DP[0] = iLL(0, 0);
 
  int pos = 0;
  LL maxNum = 0;
  LL nowCost = 0;
  int cnt = 0;
 
  while (cnt < N){
	
    cnt++;
    //今まで通った街の中でBが最大のものを保持する
    maxNum = max(maxNum, B[pos]);
    //移動できるならする
    if (nowCost + A[pos] >= 0){
      nowCost += A[pos];
      pos++;
      PRE_DP[pos] = iLL(cnt, nowCost);
    }
    //移動できないなら、今まで通った街の中でBが最大だったところに
    //滞在したことにする
    else{
      nowCost += maxNum;
    }
	
  }
 
  //探索
  LL ans = 0;
  maxNum = 0;
  for (int k = 0; k < N; k++){
    if (PRE_DP[k].first == -1)
      break;
    maxNum = max(maxNum, B[k]);
    LL n = N - PRE_DP[k].first; //余分に待機できる回数
    if (n < 0)
      continue;
    ans = max(ans, PRE_DP[k].second + n*maxNum);
  }
 
  //全部移動するパターンは怖いから別に計算する
  LL tmp = 0;
  for (int i = 0; i < N; i++){
    tmp += A[i];
    if (tmp < 0){
      tmp = -1;
      break;
    }
  }
  ans = max(ans, tmp);
 
  cout << ans << endl;
	
 
  return 0;
 
}