AOJ 2312 - Magical Girl Sayaka-chan

問題文 : 魔法少女さやかちゃん

解法 :
問題文で示されている円環が直線だと考えると, ある音符とある音符の間は、昇順になっていることが望ましい.
そこで、始点を音程のうちもっとも小さいもの, 終点を音程のうちもっとも大きいものとし, 始点->終点 にいく道を2つ作ることを考える. (これで円環が表現できる.)

どの道に割り振るかを全て確かめるとO(2^N)時間でこの問題がとけるが, ここでは
dp(a, b) -> 道Aの最後の音程がK[a], 道Bの最後の音程がK[b]
というdpテーブルをもち、メモ化再帰をしている.
こうすることで, O(N^2)時間でこの問題を解くことが出来る.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
int N, M, L;
ll K[2048];
ll SSum[100001];
ll memo[2048][2048];
 
ll pls(int r, int l)
{
    return ((SSum[r] - SSum[l]) / (ll)L);
}
 
ll saveSayaka(int l, int r)
{
    int next = max(l, r) + 1;
     
    if (memo[l][r] >= 0){
        return (memo[l][r]);
    }
     
    if (next == N - 1){
        return (pls(K[next], K[l] - 1) + pls(K[next], K[r] - 1));
    }
     
    ll left = saveSayaka(next, r) + pls(K[next], K[l] - 1);
    ll right = saveSayaka(l, next) + pls(K[next], K[r] - 1);
     
    return (memo[l][r] = min(left, right));
}
 
int main(void)
{
    scanf("%d %d %d", &N, &M, &L);
     
    for (int i = 0; i < N; i++){
        scanf("%d", &K[i]);
    }
     
    for (int i = 0; i < M; i++){
        int s;
        scanf("%d", &s);
        SSum[i + 1] = SSum[i] + s;
    }
     
    sort(K, K + N);
    memset(memo, -1, sizeof(memo));
     
    printf("%lld\n", saveSayaka(0, 0));
}