漸化式を立てる練習（２）

lines = $stdin.read
array = lines.split("\n")
N = array[0].to_i
H = array[1].split(" ").map(&:to_i)
INF = 10**9

def cost(hi, hj)
  #puts "|#{H[hi]}-#{H[hj]}|=#{(H[hi]-H[hj]).abs}"
  ans = (H[hi]-H[hj]).abs
  ans
end

dp = Array.new(N, INF)
dp[0] = 0

for j in 1...N
  dp[j] = [ dp[j-1] + cost(j-1, j), dp[j] ].min
  dp[j] = [ dp[j-2] + cost(j-2, j), dp[j] ].min if j>1
end

puts dp[N-1]

# coding: utf-8
lines = <<'EOS'
10 4
40 10 20 70 80 10 20 70 80 60
EOS

# lines = $stdin.read
array = lines.split("\n")
N,K = array[0].split(" ").map(&:to_i)
H = [0].concat(array[1].split(" ").map(&:to_i))
INF = 10**9

def cost(hi, hj)
  (H[hi]-H[hj]).abs
end

dp = Array.new(N+1, INF)
dp[1] = 0

for i in 1..N
  for j in i+1..i+K
    next if j>N
    dp[j] = [ cost(i, j) + dp[i], dp[j] ].min
  end
end

puts dp[N]

import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;
import std.math;

//string lines = q"[
//abcdeffg]";

long INF = pow(10, 9);
long[] H = [0L];

long cost(int i, int j)
{
    return abs(H[i]-H[j]).to!long;
}

void main()
{
  string lines;
  string buf;

  while (!stdin.eof) {
    buf = stdin.readln();
    lines ~= buf;
  }

  string[] array = splitLines(lines);
    
  int N = array[0].split(" ")[0].to!int;
  int K = array[0].split(" ")[1].to!int;
  array[1].split(" ").each!(a => H ~= a.to!long);
  
  long[] dp = new long[](N+1);
  foreach (ref long e; dp) {
    e = INF;
  }
  dp[1] = 0L;
  
  for (int i = 1; i <= N; i++) {
    for (int j = i+1; j <= i+K; j++) {
      if (j>N) continue;
      dp[j] = min( cost(i, j) + dp[i], dp[j] );
    }
  }
  writeln(dp[N]);
}

# coding: utf-8
lines = <<'EOS'
7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1
EOS

# lines = $stdin.read
array = lines.split("\n")
N = array[0].to_i
H = array[1].split(" ").map(&:to_i)
Item = Struct.new(:a, :b, :c)

items = [Item.new(0,0,0)]
array[1..N].each do |s|
  item = Item.new
  item.a, item.b, item.c = s.split(" ").map(&:to_i)
  items << item
end

dp = Array.new(N+1).map{Array.new(3, 0)}

for i in 1...N+1
  for j in 0...3
    dp[i][j] = [
      dp[i-1][1] + items[i].a, dp[i-1][2] + items[i].a
    ].max if j==0
    dp[i][j] = [
      dp[i-1][0] + items[i].b, dp[i-1][2] + items[i].b
    ].max if j==1
    dp[i][j] = [
      dp[i-1][0] + items[i].c, dp[i-1][1] + items[i].c
    ].max if j==2
  end
end

#dp.each{|l| p l}
puts dp.max.max

import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;

//string lines = q"[
//abcdeffg]";

void main()
{
  string lines;
  string buf;

  while (!stdin.eof) {
    buf = stdin.readln();
    lines ~= buf;
  }

  string[] array = splitLines(lines);
    
  int N = array[0].split(" ")[0].to!int;
  int W = array[0].split(" ")[1].to!int;
    
  long[] Wi = new long[](N+1);
  long[] Vi = new long[](N+1);
  Wi[0] = 0L;
  Vi[0] = 0L;

  for (int i=1; i<array.length; i++) {
    string s = array[i];
    Wi[i] = s.split(" ")[0].to!int;
    Vi[i] = s.split(" ")[1].to!int;
  }
  
  long[][] dp = new long[][](N+1,W+1);
  for (int i = 1; i < N+1; i++) {
    for (int j = 1; j < W+1; j++) {
      if (j < Wi[i]) {
        dp[i][j] = dp[i-1][j];
      } else {
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-Wi[i]] + Vi[i]);
      }
    }
  }
  writeln(dp.reduce!(max).reduce!(max));
}

# coding: utf-8
lines = <<'EOS'
6 15
6 5
5 6
6 4
6 6
3 5
7 2
EOS

#lines = $stdin.read
array = lines.split("\n")

Item  = Struct.new(:v, :w)
N,W   = array[0].split(" ").map(&:to_i)
INF = 10**10-1
V_MAX = 10**3

items = [Item.new(0,0)]
array[1..array.length].each do |s|
  item = Item.new
  item.w, item.v = s.split(" ").map(&:to_i)
  items << item
end

dp = Array.new(N+1).map{Array.new(V_MAX+1, INF)}

for i in 1...N+1
  for j in 1...V_MAX+1
    if items[i].v > j
      dp[i][j] = [dp[i-1][j], items[i].w].min
    else
      dp[i][j] = [dp[i-1][j], dp[i-1][j-items[i].v] + items[i].w].min
    end
  end
end

p dp.map{|arr| arr[1..-1].index{|n| n>W}}.max + 1