记录编号	87161	评测结果	AAAAAAAAAA
题目名称	[HNOI 2011] 任务调度	最终得分	100
用户昵称	GDFRWMY	是否通过	通过
代码语言	Pascal	运行时间	1.595 s
提交时间	2014-02-01 21:13:48	内存使用	0.17 MiB

const
  INF = 1000000000;
  RAND_MAX = 32767;
  init_TEMP = 100000;
  ITER_TIMES = 1000;
  alpha : double = 0.85;
  EPS = 1e-6;

var
  last_tag, last_pre, last_next, last, now, next, pre, tag, flag : array[0..50] of longint;
  t : array[0..50, 0..2] of longint;
  n : longint;

function max(x, y : longint) : longint;
  begin
    if x > y then exit(x) else exit(y);
  end;

procedure swap(var x, y : longint);
  var
    tmp : longint;
  begin
    tmp := x; x := y; y := tmp;
  end;

function can(ll, rr : longint) : boolean;//判断交换ll和rr是否可行
  begin
    if ll = rr then exit(false);
    if not ((flag[now[ll]] = 3) or (rr < next[ll])) then exit(false);
    if not ((flag[now[rr]] = 3) or (pre[rr] < ll)) then exit(false);
    exit(true);
  end;

procedure gen;//交换两个位置，生成新的序列
  var
    i, ll, rr : longint;
  begin
    repeat
      rr := random(n + n) + 1;
      ll := random(rr) + 1;
    until can(ll, rr);
    next[pre[ll]] := rr;
    pre[next[ll]] := rr;

    next[pre[rr]] := ll;
    pre[next[rr]] := ll;

    swap(pre[ll], pre[rr]);
    swap(next[ll], next[rr]);
    swap(now[ll], now[rr]);
    swap(tag[ll], tag[rr]); //machine A or B ?
  end;

function eval : longint;//算生成的序列需要的时间
  var
    i, ans : longint;
    time : array[ 0..50 ] of longint;
    cnt : array[ 0..2 ] of longint;
  begin
    cnt[1] := 0; cnt[2] := 0;
    fillchar(time, sizeof(time), 0);
    for i := 1 to n + n do
      begin
        cnt[tag[i]] := max(cnt[tag[i]], time[pre[i]]) + t[now[i],tag[i]];
        time[i] := cnt[tag[i]];     
      end;
    exit(max(cnt[1], cnt[2]));
  end;

function go(Temp, times : double; delta_E : longint) : boolean;   //模拟退火函数
  begin
    if (delta_E<0) then exit(true);
    exit((random(RAND_MAX) / RAND_MAX) < exp(-delta_E / (Temp + ( times / ITER_TIMES * (alpha - 1) * Temp))));
  end;

procedure work;
  var
    Temp : double;
    times, e0, e1, ans : longint;
  begin
    e0 := eval;
    ans := e0;
    Temp := init_TEMP;
    while (Temp > EPS) do
      begin
        for times := 1 to ITER_TIMES do 
          begin
            last := now;
            last_tag := tag;
            last_pre := pre;
            last_next := next;
            gen;
            e1 := eval; //e1为现有情况 e0为原情况
            if e1 < ans then ans := e1;
            if (go(Temp, times, e1 - e0)) then e0 := e1 
              else
                begin
                  now := last;
                  tag := last_tag;
                  pre := last_pre;
                  next := last_next;
                end;
          end;
        Temp := Temp * alpha; //降温。。*-*
      end;
    writeln(ans);
  end;

procedure init_gen;//生成一个最初始的排列
  var
    i : longint;
  begin
    now[0] := 0;
    for i := 1 to n do
      begin
        now[i] := i;
        if flag[i]=2 then tag[i] := 2
          else tag[i] := 1;
        pre[i] := 0;
        next[i] := n + i;
      end;
    for i := 1 to n do
      begin
        now[n + i] := i;
        if flag[i] = 2 then tag[n + i] := 1
          else tag[n + i] :=2;
        pre[n + i] :=i;
        next[n + i] := n + n + 1;
      end;
    now[n + n + 1] := n + 1;
  end;

procedure pre_work;
  var
    i : longint;
  begin
    read(n);
    for i := 1 to n do
      read(flag[i], t[i,1], t[i,2]);
    t[0, 1] := 0; t[0, 2] := 0;
    t[n + 1, 1] :=0; t[n + 1, 2] :=0;
    init_gen;
  end;

begin
 assign(input,'task.in');reset(input);
  assign(output,'task.out');rewrite(output);
  randomize;
  pre_work;
  work;
  close(input);close(output);
end.