题解 P1734 【最大约数和】

# ~~能打表为什么不一步到位~~ ## 楼上的神犇已经讲过预处理的重要性了，本蒟蒻就不再多说。 ### lcc云：“无论遇到什么题，都不要害怕，解决难题的最好办法就是暴力打表。” #### 因子和打表代码贴上 ```cpp freopen("biao.txt","w",stdout); for(int i= 1;i<=1000;i++) { for(int j=i*2;j<=1000;j+=i) ysh[j] += i; } 略； for(int i=0;i<=1000;i++) cout<<dp[i]<<","; ``` 借鉴了一下楼上大佬的筛法思路，套用一下~~其实也就1000都无所谓~~ #### 然后就是关键的状态转移方程了 这道题可以想象成一个0 1背包问题，把S想象为背包的容量，把每个数想象成一个物品，他的因子和就是他的价值。 然后把S枚举一遍。 可以得到 dp[j]=max(dp[j],dp[i-j]+c[j]); ```cpp for(int i=1;i<=1000;i++) { for(int j=1;j<=i;j++) { dp[i]=max(dp[i],dp[i-j]+ysh[j]); } } ``` 一个完美的表就打好了 完整代码贴上 ```cpp #include<iostream> #include<cstdio> using namespace std; //int ysh[1001],dp[1001]; int answer[1001]={0,0,1,1,3,3,6,6,7,7,9,9,16,16,17,17,19,19,22,22,23,23,25,25,36,36,37,37,39,39,42,42,43,43,45,45,55,55,56,56,58,58,61,61,62,62,64,64,76,76,77,77,79,79,82,82,83,83,85,85,108,108,109,109,111,111,114,114,115,115,117,117,124,124,125,125,127,127,130,130,131,131,133,133,144,144,145,145,147,147,150,150,151,151,153,153,163,163,164,164,166,166,169,169,170,170,172,172,184,184,185,185,187,187,190,190,191,191,193,193,240,240,241,241,243,243,246,246,247,247,249,249,256,256,257,257,259,259,262,262,263,263,265,265,276,276,277,277,279,279,282,282,283,283,285,285,295,295,296,296,298,298,301,301,302,302,304,304,316,316,317,317,319,319,322,322,323,323,325,325,366,366,367,367,369,369,372,372,373,373,375,375,382,382,383,383,385,385,388,388,389,389,391,391,402,402,403,403,405,405,408,408,409,409,411,411,421,421,422,422,424,424,427,427,428,428,430,430,442,442,443,443,445,445,448,448,449,449,451,451,504,504,505,505,507,507,510,510,511,511,513,513,520,520,521,521,523,523,526,526,527,527,529,529,540,540,541,541,543,543,546,546,547,547,549,549,559,559,560,560,562,562,565,565,566,566,568,568,580,580,581,581,583,583,586,586,587,587,589,589,612,612,613,613,615,615,618,618,619,619,621,621,628,628,629,629,631,631,634,634,635,635,637,637,648,648,649,649,651,651,654,654,655,655,657,657,667,667,668,668,670,670,673,673,674,674,676,676,688,688,689,689,691,691,694,694,695,695,697,697,810,810,811,811,813,813,816,816,817,817,819,819,826,826,827,827,829,829,832,832,833,833,835,835,846,846,847,847,849,849,852,852,853,853,855,855,865,865,866,866,868,868,871,871,872,872,874,874,886,886,887,887,889,889,892,892,893,893,895,895,924,924,925,925,927,927,930,930,931,931,933,933,940,940,941,941,943,943,946,946,947,947,949,949,960,960,961,961,963,963,966,966,967,967,969,969,979,979,980,980,982,982,985,985,986,986,988,988,1000,1000,1001,1001,1003,1003,1006,1006,1007,1007,1009,1009,1050,1050,1051,1051,1053,1053,1056,1056,1057,1057,1059,1059,1066,1066,1067,1067,1069,1069,1072,1072,1073,1073,1075,1075,1086,1086,1087,1087,1089,1089,1092,1092,1093,1093,1095,1095,1105,1105,1106,1106,1108,1108,1111,1111,1112,1112,1114,1114,1126,1126,1127,1127,1129,1129,1132,1132,1133,1133,1135,1135,1176,1176,1177,1177,1179,1179,1182,1182,1183,1183,1185,1185,1192,1192,1193,1193,1195,1195,1198,1198,1199,1199,1201,1201,1212,1212,1213,1213,1215,1215,1218,1218,1219,1219,1221,1221,1231,1231,1232,1232,1234,1234,1237,1237,1238,1238,1240,1240,1252,1252,1253,1253,1255,1255,1258,1258,1259,1259,1261,1261,1314,1314,1315,1315,1317,1317,1320,1320,1321,1321,1323,1323,1330,1330,1331,1331,1333,1333,1336,1336,1337,1337,1339,1339,1350,1350,1351,1351,1353,1353,1356,1356,1357,1357,1359,1359,1369,1369,1370,1370,1372,1372,1375,1375,1376,1376,1378,1378,1390,1390,1391,1391,1393,1393,1396,1396,1397,1397,1399,1399,1428,1428,1429,1429,1431,1431,1434,1434,1435,1435,1437,1437,1444,1444,1445,1445,1447,1447,1450,1450,1451,1451,1453,1453,1464,1464,1465,1465,1467,1467,1470,1470,1471,1471,1473,1473,1483,1483,1484,1484,1486,1486,1489,1489,1490,1490,1492,1492,1504,1504,1505,1505,1507,1507,1510,1510,1511,1511,1513,1513,1698,1698,1699,1699,1701,1701,1704,1704,1705,1705,1707,1707,1714,1714,1715,1715,1717,1717,1720,1720,1721,1721,1723,1723,1734,1734,1735,1735,1737,1737,1740,1740,1741,1741,1743,1743,1753,1753,1754,1754,1756,1756,1759,1759,1760,1760,1762,1762,1774,1774,1775,1775,1777,1777,1780,1780,1781,1781,1783,1783,1806,1806,1807,1807,1809,1809,1812,1812,1813,1813,1815,1815,1822,1822,1823,1823,1825,1825,1828,1828,1829,1829,1831,1831,1842,1842,1843,1843,1845,1845,1848,1848,1849,1849,1851,1851,1861,1861,1862,1862,1864,1864,1867,1867,1868,1868,1870,1870,1882,1882,1883,1883,1885,1885,1888,1888,1889,1889,1891,1891,2040,2040,2041,2041,2043,2043,2046,2046,2047,2047,2049,2049,2056,2056,2057,2057,2059,2059,2062,2062,2063,2063,2065,2065,2076,2076,2077,2077,2079,2079,2082,2082,2083,2083,2085,2085,2095,2095,2096,2096,2098,2098,2101,2101,2102,2102,2104,2104,2116,2116,2117,2117,2119,2119,2122,2122,2123,2123,2125,2125,2148,2148,2149,2149,2151,2151,2154,2154,2155,2155,2157,2157,2164,2164,2165,2165,2167,2167,2170,2170,2171,2171,2173,2173,2184,2184,2185,2185,2187,2187,2190,2190,2191,2191,2193,2193,2203,2203,2204,2204,2206,2206,2209,2209,2210,2210,2212,2212,2224,2224,2225,2225,2227,2227,2230,2230,2231,2231,2233,2233,2280,2280,2281,2281,2283,2283,2286,2286,2287,2287,2289,2289,2296,2296,2297,2297,2299,2299,2302,2302,2303,2303,2305,2305,2316,2316,2317,2317,2319,2319,2322,2322,2323,2323,2325,2325,2335,2335,2336,2336,2338}; int main() { /* freopen("biao.txt","w",stdout); for(int i= 1;i<=1000;i++) { for(int j=i*2;j<=1000;j+=i) ysh[j] += i; } for(int i=1;i<=1000;i++) { for(int j=1;j<=i;j++) { dp[i]=max(dp[i],dp[i-j]+ysh[j]); } } for(int i=0;i<=1000;i++) cout<<dp[i]<<",";*/ int n; cin>>n; cout<<answer[n]; return 0; } ```