- 1
- var dp: array[0..110000] of int64;
- 2 a,
- b,
- c: array[0..110000] of longint;
- 3 n,
- i: longint;
- 4 5
- function clac(x, y: longint) : int64;
- 6 begin 7
- if a[x] = b[y] then exit(1 << 60) 8
- else exit(abs(a[x] - b[y]));
- 9 end;
- 10 11 procedure swap(var x, y: longint);
- 12
- var t: longint;
- 13 begin 14 t: =x;
- x: =y;
- y: =t;
- 15 end;
- 16 17
- function min(x, y: int64) : int64;
- 18 begin 19
- if xthen exit(x);
- 20 exit(y);
- 21 end;
- 22 23 procedure qsort(l, r: longint);
- 24
- var i, j, mid: longint;
- 25 begin 26 i: =l;
- j: =r;
- mid: =c[(l + r) >> 1];
- 27 repeat 28
- while mid > c[i] do inc(i);
- 29
- while middo dec(j);
- 30
- if i <= j then 31 begin 32 swap(c[i], c[j]);
- 33 inc(i);
- dec(j);
- 34 end;
- 35 until i > j;
- 36
- if lthen qsort(l, j);
- 37
- if ithen qsort(i, r);
- 38 end;
- 39 40 begin 41 assign(input, 'bzoj1237. in ');
- reset(input);
- 42 assign(output, 'bzoj1237.out');
- rewrite(output);
- 43 readln(n);
- 44
- for i: =1 to n do read(a[i], b[i]);
- 45
- for i: =1 to n do c[i] : =a[i];
- 46 qsort(1, n);
- 47
- for i: =1 to n do a[i] : =c[i];
- 48
- for i: =1 to n do c[i] : =b[i];
- 49 qsort(1, n);
- 50
- for i: =1 to n do b[i] : =c[i];
- 51 dp[1] : =clac(1, 1);
- 52 dp[2] : =min(clac(1, 2) + clac(2, 1), dp[1] + clac(2, 2));
- 53
- for i: =3 to n do 54 begin 55 dp[i] : =1 << 60;
- 56 dp[i] : =min(dp[i], dp[i - 1] + clac(i, i));
- 57 dp[i] : =min(dp[i], dp[i - 2] + clac(i, i - 1) + clac(i - 1, i));
- 58 dp[i] : =min(dp[i], dp[i - 3] + clac(i - 2, i) + clac(i - 1, i - 2) + clac(i, i - 1));
- 59 dp[i] : =min(dp[i], dp[i - 3] + clac(i - 2, i - 1) + clac(i - 1, i) + clac(i, i - 2));
- 60 dp[i] : =min(dp[i], dp[i - 3] + clac(i - 2, i) + clac(i - 1, i - 1) + clac(i, i - 2));
- 61 end;
- 62
- if dp[n] > (1 << 59) then writeln( - 1) 63
- else writeln(dp[n]);
- 64 close(input);
- 65 close(output);
- 66 end.
来源: http://www.bubuko.com/infodetail-1958647.html