acm程序設(shè)計之dp-全文預(yù)覽
【正文】 t argc, char *argv[]) ? { ? int x,y,z。yz) ? { ? if (data[x][y][z]==1) ? data[x][y][z]=inf(x,y,z1)+inf(x,y1,z1)inf(x,y1,z)。 ? long long inf(int x,int y,int z) ? { if (x=0||y=0||z=0) return 1。t we? Consider a threeparameter recursive function w(a, b, c): ? if a = 0 or b = 0 or c = 0, then w(a, b, c) returns: 1 ? if a 20 or b 20 or c 20, then w(a, b, c) ? returns: w(20, 20, 20) ? if a b and b c, then w(a, b, c) ? returns: w(a, b, c1) + w(a, b1, c1) w(a, b1, c) ? otherwise it ? returns: w(a1, b, c) + w(a1, b1, c) + w(a1, b, c1) w(a1, b1, c1) This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion. 2020/9/16 6 ? input ? The input for your program will be a series of integer triples, one per line, until the endoffile flag of 1 1 1. Using the above technique, you are to calculate w(a, b, c) efficiently and print the result. 2020/9/16 7 ? output ? Print the value for w(a,b,c) for each triple. 2020/9/16 8 ? sample_input ? 1 1 1 ? 2 2 2 ? 10 4 6 ? 50 50 50 ? 1 7 18 ? 1 1 1 sample_output w(1, 1, 1) = 2 w(2, 2, 2) = 4 w(10, 4, 6) = 523 w(50, 50, 50) = 1048576 w(
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1