魔法少女さやかちゃん (AOJ 2312)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2312

問題

略

解法

DPで解く。大きい数値は隣接して置いた方が良いので、一番大きい数値を置いた後に、残りの数値を大きい順に左端か右端に順々に置いていけば良い。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n, m, L;
int card[2010];
int seq[100010];
ll sum[100010];
ll memo[2010][2010];

inline ll score(int l, int r) {
  l = card[l]; r = card[r];
  if (l > r) { swap(l, r); }
  return (sum[r + 1] - sum[l]) / L;
}

ll calc(int left, int right) {
  if (memo[left][right] != -1) { return memo[left][right]; }
  int index = max(left, right) + 1;
  if (index == n) {
    return score(left, right);
  }
  ll ret = 1LL << 60;
  ret = min(ret, calc(index, right) + score(left, index));
  ret = min(ret, calc(left, index) + score(right, index));
  return memo[left][right] = ret;
}

int main() {
  while (scanf("%d %d %d", &n, &m, &L) > 0) {
    MEMSET(memo, -1);
    MEMSET(sum, 0);
    REP(i, n) {
      int v = scanf("%d", &card[i]);
      card[i]--;
      assert(v == 1);
    }
    REP(i, m) {
      int v = scanf("%d", &seq[i]);
      assert(v == 1);
    }
    sum[0] = 0;
    REP(i, 100000) {
      sum[i + 1] = sum[i] + seq[i];
    }
    sort(card, card + n);
    reverse(card, card + n);
    ll ans = calc(0, 0);
    printf("%lld\n", ans);
  }
}