acm程序設(shè)計(jì)之dp(已修改)
2025-08-30 19:02 本頁(yè)面
【正文】 ACM程序設(shè)計(jì) 東北林業(yè)大學(xué) 陳宇 2020/9/16 2 今天你 AC 了嗎？ 2020/9/16 3 第 7講 DP（二） 2020/9/16 4 我校的 ACM在線評(píng)測(cè)系統(tǒng) ? ? 課件下載地址： ? 2020/9/16 5 Function Run Fun nefu16 ? We all love recursion! Don39。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(1, 7, 18) = 1
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1