(id:asi1024による)JOI本選予想問題：問題１ 本棚 (Book Shelf)

問題文

http://d.hatena.ne.jp/asi1024/20101224/1293157742

解法

まあ、パッと見貪欲で終了って言ってもいいけど、詳しく解説してみる。簡単なDPから貪欲にする方針で。

dp[i] := 本棚 i..M を修理するのにかかる最低時間

とすると求める答は dp[1] で、このDPは次のように計算できる。

dp[i] <- infinity
j <- i
while 棚 i..j を1度に修理することが可能である:
    dp[i] <- min(dp[i], dp[j] + 1)
    j <- j+1

最初は dp[M] <- 1 としておけばいい。

ここで dp は明らかに単調減少だから、1度に修理する棚をできるだけ多くすればいいので、貪欲法で最適解が出せる。

他の考え方(といってもほぼ同じだけど)としては、本棚 1..M を修理する最適解は 1..M をいくつかの範囲に分割したもので表せることから考える。

その最適な範囲の集合の中には必ず 1 を含む範囲があるので、それを出来るだけ広げても集合の要素数が変わらないことから貪欲法で最適解が得られることが示せる。

と、書いてみたけどまあ「パッと見貪欲法」で十分な気がする。

ソース

#include<cstdio>
#include<algorithm>

using namespace std;

int N, M, W, P[1<<20];

int main()
{
  scanf("%d%d%d", &M, &W, &N);
  for(int i=0; i<M; ++i) scanf("%d", &P[i]);
  if(*max_element(P, P+M) > W) { puts("-1"); return 0; }
  int sol=1, sum=0, n=0;
  for(int i=0; i<M; ++i) {
    if(n==N || sum+P[i] > W) { sol++; sum=P[i]; n=1; }
    else { sum+=P[i]; n++; }
  }
  printf("%d\n", sol);
  return 0;
}