Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 6 Solved: 6
写一个程序,给出D(2≤D≤10)个数字,按原顺序在数字间加+,一,×算出24,且不使用括
号.优先级按正常的优先级处理,即先做乘法后做加减法.输出有多少种不同的方案数.
第1行:一个整数D.
第2到D+1行:D个整数,在1到50之间.
输出方案总数.
5 6 4 2 8 16
4 样例说明 四种方法分别是6x4x2-8-16,6-4- 2+8+16,6x4-2 x8+16,6×4+2×8-16.
题解:直接O(3N)都能过。。。水水哒。。。
(还有话说USACO Orange/Green/Blue 这玩意是什么鬼= =,别告诉我Orange=Bronze阿阿阿QAQ,@bx2k @Recursionsheep @acphile @wnjxyk)
1 const d:array[1..3] of char=('+','-','*');
2 var
3 i,j,k,l,m,n:longint;
4 a,b:array[0..20] of longint;
5 function calc:int64;
6 var i:longint;a1,a2,a3:int64;
7 begin
8 a1:=0;a2:=a[1];a3:=1;
9 for i:=2 to n do
10 begin
11 case b[i-1] of
12 1:BEGIN
13 if a3=1 then a1:=a1+a2 else a1:=a1-a2;
14 a2:=a[i];a3:=1;
15 end;
16 2:begin
17 if a3=1 then a1:=a1+a2 else a1:=a1-a2;
18 a2:=a[i];a3:=2;
19 end;
20 3:begin
21 a2:=a2*a[i];
22 end;
23 end;
24 end;
25 if a3=1 then a1:=a1+a2 else a1:=a1-a2;
26 calc:=a1;
27 end;
28 procedure dfs(x:longint);inline;
29 var i:longint;
30 begin
31 if x>=n then
32 begin
33 if calc=24 then inc(l);
34 exit;
35 end;
36 for i:=1 to 3 do
37 begin
38 b[x]:=i;
39 dfs(x+1);
40 end;
41 end;
42 begin
43 readln(n);
44 for i:=1 to n do readln(a[i]);
45 l:=0;
46 dfs(1);
47 writeln(l);
48 end.