テキトーなメモ帳

テキトーなメモ帳

AOJ:2312 Magical Girl Sayaka-chan

動的計画法です。


まず音符を音楽的美しさ順でソートします(昇順でも降順でもどっちでもいい、ソースコードだと降順なのでこっちで説明していく。)
以下ソート後の各音符の順番のことをindexとします。


つぎに、index::=0の音符を始点とし、音楽的美しさ順で直線的に音符を連結していきます。(ただし、始点から異なる線分が2本伸びていると考え、そのどちらかの線分上に連結された音符は置かれているとする)
そして、最後に端点同士を連結し、端点が連結されたもの同士の精神力を比較していくことで、消費される精神力の最小値を求めることができます。


具体的には、
まず、直線的に音符を連結する時に

dp[新たに連結された音符(つまり同時に端点になる)のindex][もう片方の端点の音符のindex] ::= 消費される精神力の最小値

となるように、消費される精神力の最小値を記録していきます。


そして、最後に、「 res = min(dp[num_of_notes - 1][i] + compute(i,num_of_notes - 1),res)」により
端点を連結したもの同士の精神力の比較を行っていけば解くことができます。


入力例1を図示すると以下のようになります。
(星で囲っているのはindex、compute(i,j)::= index iとindex jの間の連結コスト)


なお、直線的に音符を連結するというアイディアは以下のページを参考にさせていただきました。
http://d.hatena.ne.jp/k_operafan/20111117/1321506213

#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;
 
const static int tx[] = {0,1,1,1,0,-1,-1,-1};
const static int ty[] = {-1,-1,0,1,1,1,0,-1};
 
static const double EPS = 1e-8;


int num_of_notes;
int num_of_beauty;
ll force_of_repulsion;
ll sum[200001];
ll dp[2001][2001];
int notes[2001];
ll beauty[100001];

ll compute(int i,int j){
  ll lhs = sum[notes[i]];
  ll rhs = (notes[j] - 1 < 0 ? 0 : sum[notes[j] - 1]);

  return (lhs - rhs) / force_of_repulsion;
}

int main(){
  while(~scanf("%d %d %lld",
	       &num_of_notes,
	       &num_of_beauty,
	       &force_of_repulsion)){

    for(int note_idx = 0; note_idx < num_of_notes; note_idx++){
      scanf("%d",notes + note_idx);
      notes[note_idx]--;
    }

    memset(sum,0,sizeof(sum));

    for(int beauty_idx = 0; beauty_idx < num_of_beauty; beauty_idx++){
      scanf("%d",beauty + beauty_idx);
      sum[beauty_idx] = (beauty_idx - 1 >= 0 ? sum[beauty_idx - 1] : 0) + beauty[beauty_idx];
    }

    sort(notes,notes + num_of_notes);
    reverse(notes,notes + num_of_notes);

    memset(dp,0x3f,sizeof(dp));

    dp[0][0] = 0;
    for(int i=0;i<num_of_notes;i++){
      int next = i + 1;
      if(next >= num_of_notes) break;
      for(int j=0;j<=i;j++){
	dp[next][j]
	  = min(dp[next][j],dp[i][j] + compute(i,next));

	dp[next][i]
	  = min(dp[next][i],dp[i][j] + compute(j,next));
      }
    }

    ll res = LINF;
    for(int i=0;i<num_of_notes;i++){
      res = min(dp[num_of_notes - 1][i] + compute(i,num_of_notes - 1),res);
    }
    
    printf("%lld\n",res);
  }
}