排队买票2种方法

排队买票

Time Limit:1000MS  Memory Limit:65536K Total Submit:240 Accepted:81

Description

一个演唱会即将举行，现有 N 个歌迷排队买票，一个人一张，而售票处规定，一个人每次最多买两张，假设买一张票的时间为 Ti （ 1<=i<=N ） , 队伍中相邻的歌迷（第 j 个人和第 j+1 个人）也可以由其中的一个人买两张票的时间为 Ri, 假如 Rj < Ti+Tj+1, 这样做可以缩短后面的歌迷等待的时间，现给出 N ， Ti,Rj, 求每个人买到票的最短时间和方法。

Input

Output

Sample Input

４ 1 2 3 4 4 4 5

Sample Output

8

Source

elba

公式：

    顺推：

   。。。。。。

   a[i]+a[i+1]>b[i]

    then f[i]:=f[i]+b[i-1];

    else f[i]:=f[i]+a[i]; 

var i,j,k,n,m:longint; a,f,b:array[-100..10000]of longint; begin readln(n); for i:=1 to n do begin read(a[i]); end; for i:=1 to n-1 do begin read(b[i]); end; k:=0; f[1]:=a[1]; for i:=2 to n do if f[i-1]+a[i]>f[i-2]+b[i-1] then f[i]:=f[i-2]+b[i-1] else f[i]:=f[i-1]+a[i]; k:=0; writeln(f[n]); end. .....

var

  i,j,k,n,m:longint;   a,f,b:array[-10..20000]of longint; begin   readln(n);   for i:=1 to n do     begin       read(a[i]);     end;   for i:=1 to n-1 do   begin     read(b[i]);     if i=1 then b[i-1]:=b[i];   end;   k:=0;   for i:=n downto 1 do     begin     if k<>1 then       if ((a[i-2]+a[i-1]>=b[i-2]) and (b[i-1]+a[i-2]<b[i-2]+a[i]) and (a[i]+a[i-1]>=b[i-1]))       then begin              f[i]:=f[i]+b[i-1];              k:=1;           end else         begin           k:=0;           f[i]:=f[i]+a[i];         end       else k:=0;     end;   k:=0;   for i:=1 to n do     k:=k+f[i];   writeln(k); end.