P1734 最大约数和 新解法

· · 闲话

P1734 最大约数和 题解

说在前面

我在做 P1734 最大约数和的时候，发现我的做法和其他题解不一样，就来分享一波。

思路

1、打表

假如在考试时做这种题，循环很可能 TLE ，最好就是打表。
问：打表不是会 MLE 吗？
答：如果打表都 MLE 了，双重循环不就 TLE 得更厉害了。
打表打的是从 1 至 1000 所有数的约数之和。
打表代码如下： 

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    cout << 0;
    for (int i = 1; i <= 1000; i++) {
        int t = 0;
        for (int j = 1; j < i; j++)
            if (i % j == 0)
                t += j;
        cout << ", " << t;
    }   
    return 0;
}

2、动态规划

把打表出来的数存进 a 数组中，进行动态规划。由于每个数都只能选一个，所以是 01 背包问题。 因此，套用 01 背包问题的模板就行，动态规划方程如下：

dp_j=MAX_{dp_j,dp_{j-i}+a_i}

不懂的可以找oi-wiki。

3、输出

因为 dp_n 不一定是最大的，所以要循环一遍，取最大值输出。

所以，就可以写代码了。

AC 代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, a[1005] = {0, 0, 1, 1, 3, 1, 6, 1, 7, 4, 8, 1, 16, 1, 10, 9, 15, 1, 21, 1, 22, 11, 14, 1, 36, 6, 16, 13, 28, 1, 42, 1, 31, 15, 20, 13, 55, 1, 22, 17, 50, 1, 54, 1, 40, 33, 26, 1, 76, 8, 43, 21, 46, 1, 66, 17, 64, 23, 32, 1, 108, 1, 34, 41, 63, 19, 78, 1, 58, 27, 74, 1, 123, 1, 40, 49, 64, 19, 90, 1, 106, 40, 44, 1, 140, 23, 46, 33, 92, 1, 144, 21, 76, 35, 50, 25, 156, 1, 73, 57, 117, 1, 114, 1, 106, 87, 56, 1, 172, 1, 106, 41, 136, 1, 126, 29, 94, 65, 62, 25, 240, 12, 64, 45, 100, 31, 186, 1, 127, 47, 122, 1, 204, 27, 70, 105, 134, 1, 150, 1, 196, 51, 74, 25, 259, 35, 76, 81, 118, 1, 222, 1, 148, 81, 134, 37, 236, 1, 82, 57, 218, 31, 201, 1, 130, 123, 86, 1, 312, 14, 154, 89, 136, 1, 186, 73, 196, 63, 92, 1, 366, 1, 154, 65, 176, 43, 198, 29, 148, 131, 170, 1, 316, 1, 100, 141, 203, 1, 270, 1, 265, 71, 104, 37, 300, 47, 106, 105, 226, 31, 366, 1, 166, 75, 110, 49, 384, 39, 112, 77, 284, 31, 234, 1, 280, 178, 116, 1, 332, 1, 202, 153, 218, 1, 312, 53, 184, 83, 194, 1, 504, 1, 157, 121, 190, 97, 258, 33, 232, 87, 218, 1, 476, 35, 130, 177, 255, 1, 270, 45, 328, 129, 134, 1, 456, 59, 214, 93, 208, 1, 450, 1, 286, 175, 140, 97, 396, 1, 142, 137, 440, 1, 294, 1, 220, 195, 218, 49, 531, 18, 250, 101, 226, 1, 390, 65, 274, 183, 152, 37, 568, 51, 154, 105, 316, 67, 396, 1, 364, 107, 266, 1, 528, 1, 160, 309, 244, 1, 330, 41, 442, 111, 254, 37, 523, 109, 166, 113, 302, 55, 534, 1, 256, 161, 170, 73, 656, 1, 211, 117, 416, 43, 438, 57, 316, 231, 176, 1, 492, 1, 394, 209, 404, 1, 366, 77, 274, 219, 182, 1, 810, 20, 184, 169, 420, 79, 378, 1, 376, 177, 314, 61, 524, 1, 274, 249, 344, 43, 582, 1, 460, 131, 194, 1, 636, 191, 196, 185, 298, 1, 618, 41, 463, 135, 200, 85, 696, 1, 202, 241, 561, 1, 414, 45, 310, 321, 314, 49, 672, 1, 346, 141, 316, 67, 522, 89, 466, 143, 302, 1, 924, 1, 214, 201, 386, 133, 438, 69, 328, 243, 362, 1, 808, 1, 334, 285, 334, 43, 450, 1, 640, 300, 314, 1, 620, 95, 226, 153, 568, 1, 759, 53, 346, 155, 230, 217, 744, 1, 232, 261, 548, 1, 690, 1, 466, 303, 236, 1, 806, 75, 394, 161, 428, 55, 486, 145, 532, 225, 242, 1, 1032, 51, 244, 285, 447, 103, 606, 1, 442, 167, 536, 1, 684, 47, 346, 441, 496, 79, 510, 1, 592, 171, 254, 1, 1056, 107, 358, 225, 388, 1, 786, 81, 511, 287, 260, 109, 716, 59, 394, 177, 740, 1, 648, 1, 400, 467, 266, 49, 960, 24, 442, 249, 588, 55, 546, 113, 484, 183, 272, 145, 1140, 1, 274, 185, 590, 115, 798, 1, 418, 257, 566, 49, 888, 87, 280, 357, 424, 1, 690, 57, 928, 303, 284, 1, 780, 119, 286, 401, 512, 1, 870, 1, 604, 195, 434, 169, 1075, 1, 343, 197, 680, 91, 594, 65, 526, 507, 296, 1, 1008, 51, 490, 201, 586, 1, 846, 269, 454, 203, 410, 1, 1260, 1, 454, 281, 460, 193, 618, 1, 652, 351, 506, 61, 1026, 1, 310, 393, 824, 1, 630, 1, 724, 339, 314, 97, 1112, 156, 316, 333, 478, 55, 1242, 1, 568, 215, 320, 133, 876, 161, 442, 297, 890, 1, 654, 1, 700, 411, 434, 1, 1167, 71, 652, 373, 496, 1, 666, 137, 646, 305, 494, 1, 1356, 1, 334, 345, 596, 295, 816, 53, 508, 227, 554, 73, 1344, 1, 340, 565, 605, 1, 690, 105, 940, 231, 470, 1, 1136, 143, 514, 233, 676, 67, 1038, 1, 526, 555, 350, 145, 1104, 59, 352, 237, 1036, 1, 978, 57, 820, 447, 356, 109, 972, 1, 586, 329, 638, 55, 1014, 293, 544, 243, 362, 1, 1698, 111, 421, 245, 550, 205, 870, 1, 952, 364, 602, 61, 1004, 1, 370, 633, 776, 79, 900, 1, 856, 379, 554, 1, 1176, 155, 376, 345, 764, 115, 1122, 1, 736, 255, 506, 157, 1484, 1, 382, 393, 1040, 1, 774, 117, 580, 639, 386, 73, 1276, 1, 958, 261, 586, 1, 942, 217, 694, 439, 392, 61, 1572, 83, 514, 417, 983, 163, 798, 1, 598, 267, 650, 121, 1548, 75, 400, 501, 604, 1, 1122, 65, 1153, 369, 404, 85, 1100, 347, 538, 273, 722, 1, 1368, 1, 868, 275, 554, 169, 1416, 63, 412, 637, 944, 1, 834, 1, 736, 663, 614, 1, 1356, 1, 682, 281, 946, 193, 846, 173, 844, 443, 422, 1, 2040, 30, 424, 285, 640, 253, 1026, 217, 826, 287, 824, 61, 1164, 1, 634, 705, 764, 1, 1158, 1, 988, 483, 434, 1, 1656, 179, 436, 361, 924, 91, 1290, 81, 778, 401, 566, 373, 1196, 1, 442, 297, 1352, 1, 1341, 1, 880, 555, 446, 1, 1392, 135, 730, 561, 676, 67, 906, 185, 1144, 447, 452, 61, 1921, 71, 610, 505, 806, 187, 918, 1, 688, 417, 1106, 1, 1568, 95, 460, 573, 694, 139, 1242, 1, 1240, 311, 464, 85, 1764, 253, 466, 425, 962, 1, 1374, 209, 706, 315, 470, 361, 1794, 1, 694, 317, 1076, 1, 954, 65, 916, 975, 638, 1, 1292, 87, 910, 321, 1208, 1, 1152, 197, 724, 483, 482, 145, 2088, 32, 634, 441, 730, 199, 1338, 1, 1027, 471, 794, 1, 1576, 147, 490, 761, 946, 1, 990, 101, 1414, 449, 494, 1, 1536, 203, 634, 549, 972, 67, 1818, 1, 1024, 335, 734, 205, 1356, 1, 502, 521, 1340}, dp[1005], ans;//打表
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = n; j >= i; j--)
            dp[j] = max(dp[j], dp[j - i] + a[i]);//动态规划
    for (int i = 1; i <= n; i++)
        ans = max(dp[i], ans);//取最大值
    cout << ans;
    return 0;
}

完结撒花 🎇 ！