寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C++ #Volume23 : 2312 - Magical Girl Sayaka-chan

Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。

・問題 "Magical Girl Sayaka-chan"
https://onlinejudge.u-aizu.ac.jp/problems/2312
魔法少女さやかちゃん
僕が作成、提出したコードは、以下のとおりです。

Aizu Online Judge in C++ #Volume23 : 2312 - Magical Girl Sayaka-chan
/*
Aizu Online Judge in C++ #Volume23 : 2312 - Magical Girl Sayaka-chan
https://onlinejudge.u-aizu.ac.jp/problems/2312
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,m,l,k[2020],s[100010],dp[2020][2020];
ll f(ll a,ll b){
    return (s[k[b]]-s[k[a]-1])/l;
}
ll DFS(ll a,ll b,ll c){
    if(dp[a][b]!=-1){
        return dp[a][b];
    }
    if(c==n){
        return dp[a][b]=max(f(a,c-1),f(b,c-1));
    }
    if(dp[a][b]!=-1){
        return dp[a][b];
    }
    return dp[a][b]=min(DFS(c,b,c+1)+f(a,c),DFS(a,c,c+1)+f(b,c));
}
int main(void){
    memset(dp,-1,sizeof(dp));
    cin>>n>>m>>l;
    for(ll i=0;i<n;i++){
        cin>>k[i];
    }
    for(ll i=0;i<m;i++){
        cin>>s[i+1];
        s[i+1]+=s[i];
    }
    sort(k,k+n);
    cout<<DFS(0,0,1)<<endl;
    return 0;
}

この問題、魔法少女まどか☆マギカの設定と共通点が多すぎません?元ネタは絶対それですよね...。

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/