OI We S

在很久很久以前，有一个动物村庄，那里是猪的乐园（^_^），村民们勤劳、勇敢、善良、团结……
不过有一天，最小的小小猪生病了，而这种病是极其罕见的，因此大家都没有储存这种药物。所以晴天小猪自告奋勇，要去采取这种药草。于是，晴天小猪的传奇故事便由此展开……

这一天，他来到了一座深山的山脚下，因为只有这座深山中的一位隐者才知道这种药草的所在。但是上山的路错综复杂，由于小小猪的病情，晴天小猪想找一条需时最少的路到达山顶，但现在它一头雾水，所以向你求助。
山用一个三角形表示，从山顶依次向下有1段、2段、3段等山路，每一段用一个数字T（1<=T<=100）表示，代表晴天小猪在这一段山路上需要爬的时间，每一次它都可以朝左、右、左上、右上四个方向走（**注意**：在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段）。
晴天小猪从山的左下角出发，目的地为山顶，即隐者的小屋。

输入格式 第一行有一个数n（2<=n<=1000），表示山的高度。
从第二行至第n+1行，第i+1行有i个数，每个数表示晴天小猪在这一段山路上需要爬的时间。

输出格式
一个数，即晴天小猪所需要的最短时间。

样例输入
5 1 2 3 4 5 6 10 1 7 8 1 1 4 5 6
样例输出
10

时间限制
各个测试点1s

注释
在山的两侧的走法略有特殊，请自己模拟一下，开始我自己都弄错了……

来源
Sunnypig

分析
本题是经典DP数字三角形的一个加强版。说是加强，是因为注释里的那句话。这题有两种做法，从上往下推和从下往上推，显然前者更简单一些。推状态转移方程的时候只需要想在某一点可以走到那一点。题目中说从一点可以向左上，右上，左，右走，这样方程就很显然了。 F[i, j] = MAX ( F[i, j], F[i, j-1]+A[i, j], F[i, j+1]+A[i, j], F[i-1, j-1]+A[i, j], F[i-1, j]+A[i, j]){2<=i<=n, 1<=j<=i}; 最后F[n, 1]就是答案了。

===================我是华丽的分割线======================
//ALGO:DP(O(N^2))
//PROG:VOJ1006
const
    maxn = 1001;
    maxm = 100000;
var
    n : longint;
    f : array [0..maxn, 0..maxn] of longint;
    a : array [0..maxn, 0..maxn] of longint;
procedure Init;
var
    i, j : longint;
begin
    readln(n);
    for i := 1 to n do begin
        for j := 1 to i do begin
            read(a[i, j]);
            f[i, j] := maxm;
        end;
        readln;
    end;
end;
procedure Dp;
var
    i, j : longint;
    flag : boolean;
begin
    f[1, 0] := a[1, 1];
    f[1, 1] := a[1, 1];
    f[1, 2] := a[1, 1];
    for i := 2 to n do begin
        repeat
            flag := true;
            f[i, 0] := f[i, i];
            f[i, i+1] := f[i, 1];
            for j := 1 to i do begin
                if (f[i, j] > f[i-1, j] + a[i, j]) then begin
                    f[i, j] := f[i-1, j] + a[i, j];
                    flag := false;
                end;
                if (f[i, j] > f[i, j+1] + a[i, j]) then begin
                    f[i, j] := f[i, j+1] + a[i, j];
                    flag := false;
                end;
                if (f[i, j] > f[i, j-1] + a[i, j]) then begin
                    f[i, j] := f[i, j-1] + a[i, j];
                    flag := false;
                end;
                if (f[i, j] > f[i-1, j-1] + a[i, j]) then begin
                    f[i, j] := f[i-1, j-1] + a[i, j];
                    flag := false;
                end;
            end;
            if flag then break; 
        until false;
    end;
    writeln(f[n, 1]);
end;
BEGIN
    Init;
    Dp;
END.

有N个士兵分散在一个网格型的土地上。网格土地上每一个格子位置由一对整数坐标给出，士兵可以移动，每次移动可以让某个士兵向上、向下、向左或向右移动一个单元格。
这些士兵最后要进入某一行且排在一起（即他们最终的位置为(x,y),(x+1,y),…,(x+N-1,y),点(x,y)是任意的）。请问最少需要多少次移动才能做到？假设格子无限大，可以同时容纳无限多个士兵。

输入(warrior.in)
第一行一个整数N
下接n行每行两个整数描述一个士兵的初始坐标。数据保证没有两个士兵，他们的横坐标或者纵坐标相同。

输出(warrior.out)
最少移动次数

数据范围
30%的数据N<=10000
100%的数据N<=10^6，坐标范围[-10^8,10^8]

算法解析
实际上是一道数学题.
这道题可以分两步来做:第一步是将所有人放到一行上,第二步是将他们排到连续的一条链上.
第一步其实很简单,我们可以发现,只要放到中间那个人所在的一行上(如果n是偶数,那么只要放到中间的两个人之间任意的一行上就可以),就可以保证移动的步数最小.
第二步实际上和第一步很相似,只需要让所有人按照原来的顺序排列就可以了,只是每两个人之间的距离都变成了1.让原始状态下中间那个人成为最终这条链的中间那个人,可以保证移动次数最少,证明略过.
可以做两次qsort,实际应用上发现常数大的惊人,不过用我这个写得很ws的程序还是AC了,有好几个0.9s以上的点...好险...

程序
//for my winsty
{$APPTYPE CONSOLE}
program warrior_sqybi;
  const
    fin = 'warrior.in';
    fout = 'warrior.out';
    nn = 1000000;

  type
    arr = array[1..nn]of longint;

  var
    n, i, t, p, mid: longint;
    x, y: arr;
    s: int64;

  procedure qsort(var a: arr; l, r: longint);
    var
      i, j, d, t: longint;
    begin
      i := l;
      j := r;
      d := a[(l+r) div 2];
      repeat
        while a[i] < d do inc(i);
        while a[j] > d do dec(j);
        if i <= j then begin
          t := a[i];
          a[i] := a[j];
          a[j] := t;
          inc(i);
          dec(j);
        end;
      until i > j;
      if l < j then qsort(a, l, j);
      if i < r then qsort(a, i, r);
    end;

  begin
    assign(input, fin);
    assign(output, fout);
    reset(input);
    rewrite(output);
    readln(n);
    for i:=1 to n do
      readln(x[i], y[i]);
    qsort(y, 1, n);
    mid := y[(n+1) div 2];
    s := 0;
    for i:=1 to n do
      s := s + abs(y[i]-mid);
    qsort(x, 1, n);
    mid := x[(n+1) div 2];
    t := (n+1) div 2;
    for i:=1 to n div 2 do begin
      p := mid - (t - i);
      s := s + abs(p-x[i]);
    end;
    for i:=n div 2 + 1 to n do begin
      p := mid + (i - t);
      s := s + abs(p-x[i]);
    end;
    writeln(s);
    close(input);
    close(output);
  end.

OI We S开张了!
这里将是sqybi以及parachutes的题解库.
We Solve OI, OI We Solve!