谢谢大家,原本我想用装相问题的DP来做的,看了大家的题解,才知道自己的DP实力很不强呀,像各位大牛学习

zju 1234 Chopsticks

对于样例的数例

8,10,16; 19,22,27; 61,63,75; 71,72,88; 81,81,84; 96,98,103; 128,129,148; 134,134,139; 157,157,160

DP.

可以想到要取最优值,a,b应取相邻的两个数. 假设a在前,b在后,即当取b时肯定取a

设f为在前j个数中,取i对数的最优值.

第一情况:不取p[j]这个数--f

第二情况:取p[j]这个数为b---|f+sqr(p[j-1]-p[j])

则方程为:

f:=min{f,f+sqr(p[j-1]-p[j])}

不是排好了吗?!直接DP就行了...

Hint:

状态转移方程很短^_^

最大数据我的是197ms

to huyichen:

最小权匹配可以转成最大权匹配

这样可以用km算法

效率O(nm)，而且平均情况下效率很高

点击查看程序源码+详细题解

为什么要把身高从大到小排序啊

输入样例1：938 5000
1 2 4 10 12 15 18 18 23 32 35 40 40 45 53 60 68 68 74 79 80 89 89 94 100 106 109 115 116 117 122 123 128 131 135 138 147 156 160 160 166 170 174 174 174 180 185 186 187 189 194 196 205 213 218 222 231 232 235 240 248 256 260 269 271 272 276 284 291 294 302 305 310 315 324 330 337 346 352 355 364 372 374 380 388 395 404 404 409 413 413 417 422 426 428 435 438 445 451 460 469 472 479 479 485 490 495 501 503 509 509 513 518 519 526 526 533 539 548 554 559 562 565 574 574 577 579 582 587 588 588 594 602 610 616 623 623 628 637 639 640 647 653 653 656 657 660 669 675 677 681 686 689 698 698 703 705 713 716 717 722 730 738 745 750 753 757 760 764 764 772 778 784 787 796 805 813 818 826 834 837 840 847 854 859 865 867 875 883 884 886 889 892 893 902 909 918 926 926 935 938 945 953 957 958 961 963 968 976 983 990 994 999 1003 1004 1005 1013 1022 1030 1036 1042 1047 1050 1052 1059 1059 1067 1069 1069 1075 1083 1085 1090 1094 1101 1101 1104 1112 1119 1119 1120 1127 1136 1138 1146 1149 1152 1155 1163 1168 1175 1181 1189 1190 1198 1205 1207 1210 1214 1214 1220 1226 1231 1239 1246 1249 1252 1252 1256 1261 1262 1270 1277 1282 1290 1293 1299 1303 1307 1316 1324 1327 1328 1334 1335 1336 1344 1349 1357 1361 1362 1371 1375 1376 1384 1385 1388 1393 1395 1395 1397 1401 1401 1407 1415 1420 1423 1424 1429 1433 1439 1441 1448 1453 1461 1467 1472 1477 1486 1490 1491 1494 1503 1510 1519 1527 1527 1533 1533 1539 1542 1549 1553 1555 1555 1557 1562 1562 1562 1562 1568 1573 1576 1580 1588 1592 1592 1598 1603 1606 1613 1620 1626 1626 1628 1633 1639 1639 1642 1642 1648 1651 1654 1663 1669 1677 1677 1681 1684 1692 1699 1706 1707 1712 1717 1722 1725 1729 1735 1742 1751 1757 1762 1769 1770 1778 1778 1780 1789 1791 1797 1803 1804 1808 1809 1815 1820 1827 1828 1832 1840 1846 1846 1850 1850 1855 1855 1858 1859 1864 1872 1873 1881 1884 1886 1891 1896 1897 1906 1907 1907 1914 1919 1926 1930 1930 1934 1940 1942 1949 1957 1963 1969 1977 1986 1988 1991 1991 1994 1998 2003 2007 2012 2012 2021 2023 2031 2031 2039 2046 2054 2057 2058 2067 2072 2076 2077 2082 2083 2084 2086 2090 2097 2098 2104 2107 2107 2112 2121 2122 2130 2135 2140 2144 2153 2160 2163 2166 2174 2174 2174 2178 2180 2181 2182 2182 2191 2197 2199 2201 2202 2203 2210 2214 2223 2230 2237 2245 2246 2249 2253 2256 2261 2268 2277 2285 2286 2293 2294 2296 2301 2302 2308 2311 2314 2322 2322 2324 2328 2337 2342 2342 2343 2351 2358 2359 2363 2365 2366 2375 2375 2379 2384 2389 2393 2396 2396 2397 2400 2403 2407 2414 2415 2422 2431 2438 2443 2443 2450 2457 2457 2458 2462 2469 2470 2474 2476 2477 2477 2480 2481 2487 2494 2503 2509 2511 2520 2520 2527 2528 2532 2534 2535 2541 2545 2545 2551 2552 2552 2552 2559 2566 2567 2570 2570 2574 2574 2578 2579 2586 2588 2590 2599 2607 2614 2621 2623 2625 2631 2631 2639 2646 2654 2655 2664 2669 2669 2669 2671 2673 2677 2683 2690 2691 2691 2691 2700 2704 2711 2713 2713 2717 2719 2722 2723 2724 2726 2727 2733 2740 2744 2749 2753 2755 2760 2765 2772 2772 2776 2784 2792 2801 2808 2810 2812 2813 2819 2819 2824 2827 2828 2830 2838 2843 2844 2850 2855 2861 2869 2871 2879 2885 2891 2895 2900 2908 2916 2920 2928 2934 2942 2942 2944 2945 2951 2960 2966 2972 2981 2985 2992 2999 3000 3000 3008 3010 3016 3025 3033 3037 3043 3046 3047 3047 3052 3057 3062 3063 3072 3077 3077 3086 3095 3096 3102 3107 3109 3111 3111 3117 3120 3126 3127 3133 3140 3144 3150 3158 3162 3163 3172 3173 3175 3182 3185 3192 3200 3204 3211 3211 3220 3229 3233 3237 3244 3250 3253 3256 3258 3261 3269 3278 3281 3285 3285 3285 3294 3303 3305 3311 3319 3325 3326 3326 3335 3336 3340 3347 3352 3358 3367 3370 3371 3376 3381 3385 3390 3396 3404 3407 3415 3424 3432 3436 3444 3453 3456 3460 3467 3473 3476 3482 3490 3498 3503 3506 3509 3515 3524 3531 3539 3541 3546 3548 3555 3560 3562 3565 3570 3572 3576 3579 3585 3588 3589 3598 3607 3613 3618 3619 3620 3621 3626 3635 3639 3648 3652 3658 3664 3667 3674 3679 3682 3687 3693 3695 3695 3696 3704 3708 3717 3720 3721 3728 3736 3740 3745 3747 3756 3758 3766 3767 3767 3773 3775 3781 3783 3783 3788 3793 3798 3802 3803 3811 3817 3820 3820 3827 3831 3835 3835 3836 3838 3843 3849 3854 3856 3863 3869 3877 3883 3891 3891 3892 3898 3899 3908 3915 3920 3929 3933 3933 3935 3936 3942 3946 3954 3959 3960 3967 3967 3976 3984 3989 3990 3993 4001 4006 4006 4008 4009 4016 4023 4031 4037 4041 4049 4055 4062 4064 4069 4071 4079 4081 4086 4094 4100 4107 4109 4113 4122 4122 4123 4132 4139 4148 4156 4158 4167 4169 4169 4175 4180 4181 4186 4195 4200 4202 4210 4214 4223 4232 4235 4241 4248 4254 4261 4269 4270 4277 4280 4287 4287 4296 4298 4299 4305 4308 4313 4316 4318 4325 4328 4329 4331 4340 4345 4348 4355 4356 4362 4371 4376 4383 4386 4389 4392 4395 4400 4408 4411 4415 4415 4418 4426 4433 4438 4446 4452 4452 4461 4466 4467 4476 4484 4487 4492 4497 4499 4501 4504 4513 4516 4519 4524 4529 4531 4536 4542 4547 4548 4549 4551 4559 4563 4570 4572 4573 4578 4586 4591 4599 4605 4613 4613 4617 4626 4634 4638 4642 4650 4656 4662 4667 4667 4667 4672 4672 4673 4675 4676 4685 4690 4696 4701 4710 4717 4721 4728 4736 4740 4749 4751 4759 4759 4767 4775 4781 4783 4787 4789 4797 4801 4804 4804 4804 4804 4811 4817 4817 4818 4820 4823 4830 4839 4847 4849 4854 4861 4866 4873 4882 4888 4895 4897 4897 4899 4899 4900 4903 4905 4912 4919 4923 4928 4937 4937 4945 4947 4956 4956 4957 4965 4968 4976 4977 4979 4987 4994 5000 5003 5004 5013 5018 5024 5027 5030 5033 5034 5040 5040 5043 5049 5055 5062 5065 5065 5074 5078 5083 5092 5094 5100 5109 5117 5125 5130 5139 5145 5146 5154 5162 5166 5175 5184 5185 5193 5199 5206 5210 5213 5213 5219 5228 5237 5237 5238 5238 5246 5251 5259 5267 5269 5274 5278 5278 5282 5282 5283 5289 5291 5291 5297 5298 5305 5305 5313 5315 5321 5326 5335 5338 5342 5351 5353 5357 5365 5366 5370 5375 5377 5377 5382 5389 5393 5399 5399 5399 5406 5408 5417 5421 5423 5426 5433 5433 5440 5445 5450 5458 5463 5466 5475 5482 5485 5487 5487 5491 5500 5506 5507 5509 5517 5518 5521 5525 5531 5534 5538 5541 5545 5548 5548 5550 5556 5560 5562 5566 5570 5571 5574 5582 5591 5592 5594 5596 5598 5604 5611 5616 5616 5617 5624 5624 5628 5636 5642 5643 5644 5651 5659 5663 5665 5665 5672 5678 5685 5686 5688 5694 5694 5701 5704 5708 5711 5714 5718 5725 5732 5737 5745 5754 5759 5763 5767 5769 5771 5776 5783 5789 5789 5797 5806 5813 5816 5817 5822 5831 5837 5837 5844 5849 5850 5856 5858 5858 5860 5861 5868 5874 5878 5880 5883 5888 5891 5892 5896 5903 5908 5917 5920 5925 5933 5941 5949 5955 5955 5964 5966 5967 5973 5976 5981 5984 5986 5990 5994 5998 5999 5999 6006 6012 6015 6023 6023 6032 6032 6036 6044 6051 6059 6059 6068 6077 6082 6091 6092 6095 6096 6103 6106 6106 6113 6118 6123 6131 6136 6136 6145 6147 6152 6157 6160 6162 6169 6172 6173 6178 6182 6183 6189 6198 6200 6201 6205 6214 6220 6224 6230 6230 6232 6238 6247 6256 6260 6260 6263 6264 6267 6274 6276 6282 6283 6285 6293 6301 6302 6306 6314 6316 6318 6321 6326 6330 6338 6346 6353 6362 6365 6372 6377 6378 6385 6392 6392 6393 6400 6406 6411 6420 6420 6420 6427 6435 6438 6446 6454 6454 6457 6464 6468 6477 6479 6479 6484 6493 6502 6505 6505 6510 6519 6521 6526 6532 6541 6546 6554 6556 6557 6563 6567 6570 6575 6583 6586 6588 6594 6594 6600 6601 6606 6613 6617 6625 6634 6640 6640 6645 6648 6655 6658 6663 6670 6674 6682 6689 6695 6703 6708 6717 6722 6724 6729 6737 6745 6749 6755 6759 6767 6773 6779 6783 6790 6795 6801 6803 6808 6809 6816 6822 6831 6839 6842 6851 6853 6853 6859 6864 6870 6879 6887 6890 6897 6905 6914 6918 6922 6925 6931 6935 6940 6945 6953 6955 6964 6968 6974 6983 6988 6990 6990 6992 6992 6997 6999 7007 7013 7020 7028 7036 7040 7041 7043 7048 7053 7059 7067 7072 7079 7084 7087 7088 7089 7097 7099 7107 7113 7114 7119 7123 7132 7133 7134 7141 7141 7142 7151 7159 7163 7166 7173 7182 7183 7188 7192 7192 7198 7201 7203 7204 7210 7212 7214 7223 7227 7232 7239 7243 7245 7250 7253 7262 7264 7268 7270 7271 7279 7282 7282 7285 7294 7299 7308 7312 7321 7321 7324 7327 7327 7330 7339 7344 7348 7356 7359 7360 7360 7366 7369 7370 7379 7380 7382 7387 7394 7400 7405 7411 7413 7413 7419 7422 7428 7431 7434 7438 7442 7444 7445 7447 7452 7456 7464 7469 7472 7475 7480 7484 7490 7495 7500 7500 7504 7507 7513 7520 7529 7535 7544 7544 7550 7556 7562 7568 7577 7584 7588 7595 7597 7605 7613 7620 7620 7621 7626 7629 7631 7640 7640 7648 7657 7661 7661 7663 7669 7672 7672 7681 7690 7699 7703 7709 7715 7720 7724 7730 7732 7740 7749 7750 7757 7759 7766 7767 7769 7773 7779 7786 7793 7794 7794 7795 7801 7808 7809 7817 7826 7828 7837 7839 7843 7848 7853 7853 7862 7871 7874 7880 7889 7897 7897 7899 7907 7912 7916 7921 7923 7932 7938 7947 7950 7958 7959 7967 7970 7978 7982 7988 7991 8000 8003 8005 8010 8011 8013 8018 8024 8033 8041 8044 8050 8059 8062 8070 8074 8082 8086 8086 8094 8102 8110 8113 8117 8119 8125 8128 8137 8140 8149 8155 8155 8155 8164 8170 8179 8179 8186 8191 8192 8193 8197 8201 8209 8212 8220 8225 8227 8228 8233 8242 8243 8243 8247 8250 8256 8264 8270 8273 8273 8281 8282 8288 8295 8297 8306 8309 8317 8326 8333 8334 8335 8341 8342 8343 8351 8357 8364 8364 8368 8377 8381 8388 8396 8403 8409 8410 8419 8422 8427 8433 8438 8447 8454 8459 8467 8474 8478 8482 8491 8494 8498 8506 8508 8513 8519 8523 8527 8529 8537 8544 8546 8554 8558 8559 8560 8568 8571 8580 8587 8588 8595 8598 8598 8602 8611 8612 8618 8625 8633 8637 8640 8641 8641 8648 8656 8660 8663 8663 8672 8677 8679 8682 8687 8688 8692 8692 8700 8700 8706 8707 8712 8718 8719 8726 8731 8733 8736 8737 8738 8742 8748 8752 8752 8760 8767 8767 8769 8772 8772 8775 8775 8778 8783 8783 8783 8785 8794 8801 8801 8804 8806 8811 8811 8817 8818 8822 8828 8829 8836 8838 8840 8844 8848 8854 8854 8860 8864 8871 8873 8877 8880 8883 8885 8888 8893 8897 8898 8907 8909 8911 8916 8918 8926 8930 8933 8936 8945 8954 8957 8959 8966 8975 8979 8985 8994 9000 9002 9004 9004 9004 9009 9011 9016 9016 9017 9019 9025 9034 9034 9035 9035 9039 9046 9048 9048 9055 9063 9065 9068 9070 9073 9078 9087 9087 9087 9091 9092 9100 9108 9117 9121 9129 9134 9142 9147 9153 9156 9165 9170 9176 9182 9187 9196 9203 9205 9214 9216 9223 9232 9232 9239 9242 9248 9251 9255 9264 9265 9267 9267 9269 9275 9280 9281 9283 9288 9290 9298 9303 9307 9311 9312 9312 9319 9324 9332 9335 9340 9349 9357 9366 9372 9372 9376 9383 9392 9398 9407 9409 9414 9414 9422 9428 9428 9432 9439 9439 9444 9444 9449 9454 9454 9460 9461 9463 9470 9476 9484 9485 9487 9487 9488 9494 9494 9500 9508 9515 9518 9527 9528 9530 9530 9530 9537 9543 9551 9558 9566 9567 9569 9571 9575 9579 9587 9594 9596 9600 9600 9608 9617 9624 9633 9641 9643 9646 9651 9657 9663 9664 9669 9674 9678 9683 9691 9700 9703 9706 9709 9709 9714 9717 9718 9718 9727 9729 9733 9741 9748 9755 9760 9761 9765 9770 9772 9777 9779 9780 9787 9789 9794 9801 9806 9815 9820 9823 9825 9828 9830 9837 9840 9845 9847 9853 9859 9867 9870 9872 9878 9880 9883 9885 9885 9889 9897 9899 9905 9913 9913 9919 9924 9931 9935 9943 9945 9950 9956 9956 9956 9964 9965 9967 9970 9978 9978 9982 9988 9994 9994 10002 10011 10013 10022 10022 10023 10026 10033 10041 10041 10050 10053 10059 10061 10070 10074 10080 10087 10089 10098 10105 10105 10111 10120 10123 10125 10128 10137 10144 10145 10150 10156 10164 10166 10169 10169 10169 10169 10171 10178 10184 10191 10198 10198 10205 10206 10207 10213 10219 10226 10230 10235 10244 10250 10258 10264 10264 10267 10267 10275 10283 10287 10288 10288 10288 10289 10298 10303 10305 10305 10310 10317 10324 10331 10339 10345 10350 10350 10355 10359 10365 10369 10370 10376 10381 10390 10396 10400 10409 10415 10418 10422 10429 10430 10433 10441 10445 10449 10454 10458 10462 10470 10472 10479 10488 10492 10492 10497 10503 10512 10513 10514 10519 10527 10528 10537 10544 10545 10550 10556 10560 10565 10567 10573 10578 10580 10581 10585 10589 10597 10606 10611 10617 10617 10621 10629 10636 10644 10653 10656 10662 10671 10679 10684 10687 10694 10696 10699 10706 10714 10716 10723 10730 10739 10743 10751 10752 10758 10760 10766 10770 10771 10779 10785 10790 10791 10798 10800 10803 10805 10814 10815 10823 10830 10831 10833 10838 10841 10847 10850 10854 10859 10861 10863 10869 10873 10875 10880 10887 10896 10899 10899 10899 10899 10907 10910 10919 10920 10929 10934 10942 10950 10956 10956 10964 10973 10980 10982 10988 10995 10998 11006 11014 11020 11028 11036 11042 11051 11054 11054 11063 11070 11077 11086 11089 11094 11095 11096 11100 11100 11103 11103 11109 11118 11122 11125 11134 11141 11149 11153 11156 11163 11167 11176 11184 11184 11184 11189 11189 11198 11199 11206 11215 11223 11230 11230 11233 11236 11240 11244 11252 11257 11259 11265 11266 11272 11273 11280 11285 11288 11295 11296 11301 11308 11311 11313 11317 11323 11330 11332 11338 11343 11349 11355 11356 11361 11364 11373 11375 11377 11385 11391 11398 11407 11413 11414 11418 11422 11425 11427 11435 11438 11440 11444 11448 11453 11455 11463 11466 11466 11474 11476 11477 11478 11480 11489 11495 11498 11504 11510 11516 11516 11520 11527 11533 11539 11545 11548 11549 11552 11552 11556 11557 11562 11565 11565 11568 11572 11577 11577 11582 11587 11595 11601 11609 11617 11618 11621 11621 11630 11631 11640 11641 11648 11653 11653 11653 11658 11667 11672 11680 11680 11689 11689 11694 11695 11700 11703 11712 11716 11724 11730 11735 11737 11738 11747 11755 11757 11757 11764 11764 11765 11770 11773 11780 11782 11785 11787 11792 11795 11795 11804 11809 11813 11816 11821 11825 11829 11833 11834 11841 11848 11854 11862 11863 11863 11863 11870 11879 11882 11883 11891 11892 11896 11897 11905 11910 11912 11913 11918 11921 11926 11929 11938 11939 11940 11948 11950 11956 11957 11958 11959 11968 11973 11977 11978 11978 11983 11988 11996 11999 12006 12009 12012 12013 12015 12017 12017 12025 12033 12036 12039 12040 12044 12045 12045 12046 12050 12050 12055 12059 12059 12059 12066 12071 12080 12081 12085 12093 12095 12100 12109 12113 12120 12120 12125 12127 12130 12136 12139 12139 12147 12153 12158 12167 12168 12172 12181 12189 12196 12203 12208 12213 12216 12223 12229 12238 12239 12243 12245 12245 12246 12253 12253 12262 12269 12272 12281 12284 12292 12298 12305 12314 12316 12319 12324 12326 12329 12330 12334 12336 12338 12343 12346 12349 12354 12358 12362 12369 12371 12373 12373 12374 12377 12385 12389 12394 12403 12409 12416 12422 12431 12435 12443 12447 12456 12459 12467 12469 12475 12475 12479 12488 12493 12498 12507 12510 12512 12515 12518 12524 12530 12535 12536 12542 12545 12545 12547 12549 12549 12550 12550 12555 12557 12557 12564 12571 12571 12573 12579 12580 12584 12590 12591 12593 12602 12606 12607 12613 12618 12620 12621 12628 12632 12634 12634 12634 12642 12648 12657 12660 12661 12667 12667 12670 12677 12681 12686 12686 12690 12699 12702 12711 12718 12720 12728 12730 12730 12735 12741 12750 12754 12754 12757 12758 12767 12772 12777 12783 12783 12790 12791 12792 12801 12805 12810 12815 12818 12818 12825 12834 12835 12838 12846 12855 12859 12859 12865 12872 12872 12878 12879 12881 12887 12889 12898 12899 12902 12908 12908 12914 12921 12921 12924 12927 12934 12938 12942 12943 12948 12954 12957 12958 12959 12962 12964 12965 12967 12968 12971 12972 12977 12979 12980 12989 12997 13001 13009 13012 13012 13018 13019 13024 13033 13036 13042 13049 13051 13051 13055 13060 13069 13071 13073 13078 13083 13092 13095 13099 13103 13107 13112 13119 13128 13131 13132 13141 13141 13147 13149 13155 13156 13157 13166 13170 13179 13180 13188 13191 13196 13199 13200 13207 13212 13216 13216 13219 13222 13226 13235 13243 13245 13250 13258 13260 13269 13273 13275 13282 13287 13287 13290 13299 13300 13303 13311 13316 13318 13325 13326 13330 13335 13344 13344 13344 13348 13356 13362 13370 13376 13384 13390 13393 13398 13407 13411 13415 13422 13429 13436 13437 13446 13451 13457 13462 13465 13472 13479 13479 13487 13491 13499 13501 13505 13506 13510 13512 13512 13517 13525 13531 13535 13541 13543 13550 13550 13550 13553 13556 13557 13557 13564 13568 13577 13577 13582 13588 13597 13597 13606 13615 13619 13620 13622 13629 13638 13643 13650 13656 13656 13665 13674 13678 13687 13687 13694 13702 13705 13714 13720 13721 13726 13731 13732 13734 13741 13748 13748 13757 13760 13768 13768 13771 13779 13786 13795 13798 13803 13809 13810 13819 13824 13832 13833 13834 13836 13842 13851 13855 13859 13866 13874 13878 13883 13886 13895 13904 13911 13915 13920 13922 13922 13931 13931 13933 13935 13943 13948 13953 13961 13964 13969 13972 13978 13979 13988 13997 14001 14008 14014 14016 14020 14022 14026 14032 14037 14044 14051 14052 14056 14065 14069 14074 14077 14086 14089 14094 14102 14111 14120 14121 14123 14123 14123 14127 14136 14140 14146 14148 14155 14156 14158 14167 14167 14176 14185 14192 14196 14204 14207 14215 14222 14228 14233 14234 14240 14249 14257 14258 14262 14266 14267 14267 14274 14274 14277 14280 14280 14282 14284 14289 14290 14293 14299 14300 14309 14314 14317 14324 14328 14330 14331 14337 14345 14347 14350 14352 14355 14363 14369 14378 14386 14389 14390 14394 14398 14407 14409 14414 14416 14422 14425 14430 14430 14432 14439 14443 14445 14447 14451 14451 14457 14459 14465 14471 14472 14477 14477 14483 14492 14498 14501 14508 14511 14518 14521 14525 14528 14536 14540 14540 14546 14547 14547 14550 14554 14560 14562 14565 14565 14566 14568 14575 14577 14582 14583 14585 14587 14596 14599 14599 14606 14610 14618 14621 14622 14625 14634 14634 14643 14650 14653 14655 14663 14665 14668 14668 14674 14677 14677 14680 14681 14684 14684 14693 14695 14700 14709 14711 14713 14713 14720 14724 14728 14733 14740 14744 14746 14755 14760 14765 14774 14774 14778 14779 14785 14786 14792 14801 14809 14814 14818 14818 14819 14824 14826 14826 14835 14837 14846 14847 14849 14855 14857 14858 14860 14861 14866 14872 14875 14882 14891 14893 14901 14907 14916 14925 14927 14927 14927 14934 14937 14937 14937 14942 14946 14949 14951 14955 14958 14958 14960 14968 14976 14978 14983 14989 14997 15003 15008 15013 15022 15025 15032 15033 15039 15040 15040 15046 15055 15062 15066 15067 15069 15071 15072 15076 15077 15079 15085 15087 15096 15098 15105 15108 15114 15116 15117 15120 15127 15131 15134 15142 15144 15149 15158 15164 15171 15178 15187 15189 15193 15194 15196 15197 15206 15208 15208 15217 15217 15221 15223 15223 15228 15230 15231 15237 15244 15250 15259 15262 15266 15266 15272 15272 15274 15278 15285 15287 15288 15288 15292 15298 15302 15309 15313 15322 15329 15331 15338 15341 15350 15351 15351 15354 15362 15367 15369 15377 15380 15386 15391 15395 15399 15399 15399 15404 15411 15419 15421 15430 15433 15436 15440 15448 15451 15451 15458 15466 15474 15482 15486 15493 15493 15496 15505 15507 15513 15521 15525 15529 15529 15538 15539 15548 15550 15551 15551 15559 15562 15565 15574 15577 15579 15585 15592 15597 15600 15601 15606 15611 15617 15620 15627 15631 15637 15643 15645 15650 15655 15661 15663 15669 15675 15677 15685 15689 15695 15695 15702 15704 15707 15709 15711 15711 15714 15717 15725 15733 15736 15738 15746 15753 15757 15759 15767 15771 15778 15784 15785 15792 15797 15805 15814 15814 15815 15815 15816 15819 15828 15834 15842 15844 15851 15860 15867 15867 15875 15879 15884 15886 15886 15887 15888 15893 15898 15901 15901 15909 15918 15927 15930 15931 15932 15932 15940 15945 15945 15952 15953 15959 15959 15966 15975 15975 15979 15983 15987 15989 15991 15995 15995 16001 16010 16017 16025 16025 16029 16030 16033 16039 16047 16052 16054 16060 16065 16069 16069 16075 16082 16084 16091 16094 16097 16100 16105 16113 16113 16120 16120 16121 16125 16132 16138 16142 16145 16148 16155 16161 16164 16169 16176 16185 16190 16197 16203 16212 16213 16220 16224 16225 16228 16235 16239 16245 16250 16255 16257 16265 16273 16277 16285 16285 16287 16287 16293 16299 16299 16305 16309 16309 16316 16318 16327 16331 16332 16334 16339 16341 16341 16343 16343 16348 16355 16363 16365 16366 16368 16373 16374 16377 16378 16379 16387 16394 16399 16405 16406 16411 16412 16417 16418 16427 16428 16431 16431 16433 16436 16445 16453 16460 16469 16477 16483 16487 16492 16496 16496 16500 16503 16507 16512 16515 16521 16524 16529 16529 16529 16533 16542 16550 16557 16559 16566 16569 16576 16583 16586 16586 16592 16596 16604 16605 16614 16623 16631 16634 16636 16643 16645 16648 16650 16655 16659 16667 16669 16671 16674 16677 16686 16686 16687 16695 16700 16705 16710 16716 16717 16722 16727 16734 16739 16747 16754 16762 16768 16774 16776 16784 16792 16793 16800 16809 16816 16818 16827 16836 16837 16845 16845 16849 16856 16860 16864 16866 16869 16872 16878 16878 16885 16894 16894 16903 16912 16918 16918 16918 16919 16924 16927 16927 16932 16939 16941 16945 16951 16960 16966 16972 16979 16988 16989 16992 16998 17000 17004 17004 17005 17013 17022 17024 17024 17025 17026 17030 17037 17045 17048 17054 17055 17062 17066 17072 17080 17084 17086 17090 17095 17098 17105 17112 17121 17125 17133 17136 17140 17147 17153 17153 17157 17163 17171 17172 17177 17181 17181 17189 17193 17194 17198 17199 17208 17209 17216 17222 17226 17226 17231 17236 17238 17246 17251 17252 17255 17262 17262 17269 17270 17278 17284 17286 17292 17299 17301 17307 17314 17316 17325 17331 17336 17340 17340 17347 17347 17348 17352 17358 17361 17363 17370 17376 17381 17382 17389 17396 17402 17404 17413 17416 17421 17428 17434 17443 17450 17454 17462 17462 17463 17472 17477 17483 17484 17485 17488 17493 17500 17505 17510 17516 17523 17524 17524 17532 17533 17534 17539 17542 17542 17544 17553 17559 17566 17572 17580 17583 17592 17594 17603 17610 17612 17615 17615 17616 17616 17622 17626 17627 17635 17643 17652 17661 17664 17667 17672 17675 17684 17690 17696 17701 17706 17711 17715 17715 17722 17730 17734 17741 17746 17746 17752 17755 17761 17768 17777 17783 17783 17784 17790 17799 17803 17805 17809 17814 17820 17827 17832 17839 17845 17849 17858 17858 17866 17867 17869 17873 17878 17884 17887 17887 17889 17890 17893 17900 17909 17910 17912 17917 17921 17928 17931 17931 17935 17937 17944 17951 17960 17963 17966 17972 17973 17979 17986 17992 17998 18004 18012 18017 18026 18033 18037 18042 18051 18051 18054 18054 18060 18061 18061 18063 18068 18068 18069 18070 18079 18081 18085 18087 18091 18098 18104 18104 18106 18109 18117 18124 18127 18133 18136 18142 18145 18147 18153 18162 18171 18178 18184 18187 18190 18196 18197 18197 18199 18208 18216 18223 18232 18232 18232 18237 18245 18252 18261 18269 18276 18281 18284 18293 18301 18305 18311 18320 18324 18326 18330 18335 18341 18345 18350 18352 18359 18365 18372 18374 18376 18384 18386 18386 18391 18400 18408 18408 18416 18420 18422 18427 18433 18439 18446 18454 18454 18455 18455 18457 18462 18471 18476 18485 18493 18499 18502 18504 18507 18507 18507 18507 18508 18508 18510 18510 18516 18525 18525 18525 18532 18535 18539 18544 18551 18560 18560 18567 18573 18581 18589 18597 18602 18608 18611 18614 18618 18621 18628 18631 18640 18640 18641 18646 18647 18654 18655 18656 18662 18668 18677 18678 18685 18686 18694 18699 18699 18705 18709 18710 18719 18721 18725 18726 18734 18740 18741 18743 18751 18756 18758 18762 18762 18770 18771 18771 18772 18781 18782 18789 18792 18794 18799 18802 18808 18809 18812 18817 18819 18822 18829 18832 18833 18833 18838 18838 18839 18841 18842 18849 18853 18853 18862 18871 18876 18881 18888 18893 18893 18896 18903 18911 18912 18915 18921 18922 18924 18930 18936 18941 18946 18952 18952 18958 18960 18967 18974 18983 18991 18993 18998 19001 19002 19006 19011 19013 19021 19027 19027 19036 19040 19047 19051 19052 19060 19062 19063 19069 19077 19082 19082 19091 19098 19098 19104 19108 19116 19121 19122 19125 19134 19143 19147 19156 19156 19158 19161 19170 19178 19183 19186 19190 19196 19201 19210 19210 19219 19226 19234 19234 19241 19249 19254 19256 19263 19266 19272 19279 19282 19289 19294 19295 19302 19303 19308 19317 19319 19326 19330 19330 19332 19337 19342 19350 19355 19364 19365 19370 19372 19376 19377 19381 19389 19390 19396 19396 19402 19404 19405 19414 19414 19415 19417 19418 19420 19425 19432 19433 19439 19447 19450 19456 19463 19467 19474 19475 19477 19479 19488 19494 19496 19499 19506 19515 19524 19524 19529 19533 19537 19543 19550 19559 19567 19573 19578 19584 19591 19600 19607 19615 19623 19630 19634 19642 19643 19650 19656 19657 19659 19661 19667 19674 19683 19692 19700 19705 19708 19715 19716 19720 19721 19725 19732 19741 19747 19754 19762 19769 19773 19774 19775 19783 19784 19793 19799 19800 19801 19802 19804 19809 19818 19825 19827 19828 19834 19838 19846 19848 19854 19859 19867 19872 19879 19885 19887 19896 19903 19903 19910 19914 19919 19922 19925 19928 19936 19938 19942 19945 19950 19955 19963 19965 19969 19973 19977 19983 19988 19995 20002 20010 20014 20017 20025 20025 20027 20030 20033 20042 20048 20054 20054 20055 20057 20060 20066 20066 20072 20081 20082 20085 20087 20095 20097 20106 20113 20119 20124 20133 20142 20151 20159 20163 20172 20173 20182 20190 20197 20205 20206 20214 20216 20223 20228 20228 20237 20242 20246 20255 20259 20262 20267 20268 20277 20285 20290 20292 20296 20303 20307 20310 20318 20319 20327 20334 20338 20341 20345 20353 20356 20357 20358 20363 20367 20369 20371 20372 20378 20385 20392 20398 20402 20406 20406 20406 20410 20417 20420 20427 20436 20443 20451 20460 20469 20476 20483 20488 20491 20498 20503 20504 20505 20512 20517 20526 20533 20541 20544 20544 20552 20558 20564 20566 20567 20569 20577 20582 20589 20594 20600 20600 20606 20612 20619 20622 20623 20631 20633 20639 20646 20649 20657 20659 20661 20670 20675 20682 20687 20689 20690 20690 20696 20699 20699 20699 20700 20704 20711 20714 20720 20725 20731 20737 20740 20740 20742 20743 20743 20744 20752 20758 20763 20768 20775 20779 20785 20788 20788 20795 20803 20811 20820 20822 20828 20832 20839 20840 20846 20851 20852 20855 20864 20872 20873 20874 20881 20887 20893 20896 20903 20910 20911 20913 20914 20915 20916 20922 20928 20932 20933 20939 20945 20952 20956 20958 20967 20968 20973 20981 20987 20996 20996 21003 21009 21009 21011 21018 21023 21031 21033 21041 21048 21053 21057 21058 21060 21060 21066 21074 21076 21084 21088 21088 21093 21094 21098 21105 21105 21110 21118 21127 21135 21144 21144 21150 21156 21158 21162 21171 21180 21188 21194 21195 21196 21205 21207 21214 21221 21228 21234 21235 21242 21244 21251 21256 21264 21273 21278 21284 21284 21292 21295 21302 21310 21313 21319 21326 21333 21335 21341 21342 21350 21357 21363 21368 21375 21383 21387 21393 21400 21409 21417 21425 21428 21433 21439 21447 21456 21463 21472 21481 21487 21487 21488 21488 21497 21501 21508 21514 21514 21518 21519 21524 21526 21529 21537 21546 21550 21557 21560 21561 21567 21572 21581 21587 21588 21593 21599 21601 21606 21608 21615 21616 21625 21634 21642 21651 21653 21657 21666 21669 21673 21678 21683 21686 21692 21696 21698 21699 21699 21708 21715 21724 21726 21726 21726 21727 21730 21731 21740 21744 21748 21755 21756 21760 21765 21769 21772 21772 21776 21778 21782 21791 21799 21802 21811 21819 21821 21826 21826 21829 21834 21842 21848 21849 21854 21855 21855 21859 21861 21865 21866 21872 21873 21877 21883 21892 21899 21902 21909 21915 21918 21927 21928 21935 21938 21944 21951 21951 21954 21963 21966 21972 21980 21980 21986 21989 21995 22002 22004 22011 22011 22016 22025 22028 22036 22039 22046 22047 22049 22049 22058 22058 22058 22067 22074 22076 22084 22086 22095 22097 22104 22104 22110 22117 22117 22118 22121 22125 22125 22127 22135 22138 22139 22145 22152 22160 22165 22169 22170 22175 22175 22178 22187 22191 22200 22200 22202 22203 22207 22209 22215 22218 22227 22234 22238 22241 22248 22254 22258 22258 22264 22267 22273 22280 22285 22294 22297 22301 22301 22304 22311 22312 22312 22319 22321 22322 22329 22332 22336 22340 22341 22346 22351 22354 22359 22368 22371 22374 22377 22383 22385 22385 22388 22388 22397 22406 22414 22421 22426 22429 22436 22442 22446 22453 22457 22460 22465 22466 22467 22468
输出样例：826

倒序再搞

n，m搞反了然后调了很长时间= =
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int maxm=2005;
const int maxn=6005;
const int inf=0x3fffffff;

int a[maxn];
int n,m;
int f[maxn][maxm];

int sq(int v,int b)
{
return (a[v]-a[b])*(a[v]-a[b]);
}

int min(int a,int b)
{
return a<b?a:b;
}

int main()
{
cin>>m>>n;
int i,j;
for(i=n;i>=1;i--)
{
scanf("%d",&a[i]);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
f[i][j]=inf;
}
}
for(i=1;i<=m;i++)
{
for(j=i*3;j<=n;j++)
{
f[j][i]=min(min(f[j][i],f[j-1][i]),f[j-2][i-1]+sq(j,j-1));
}
}

cout<<f[n][m]<<endl;
return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 20220 KiB, score = 5
测试数据 #1: Accepted, time = 15 ms, mem = 20220 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 20220 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 20224 KiB, score = 5
测试数据 #4: Accepted, time = 15 ms, mem = 20224 KiB, score = 5
测试数据 #5: Accepted, time = 15 ms, mem = 20224 KiB, score = 5
测试数据 #6: Accepted, time = 15 ms, mem = 20224 KiB, score = 5
测试数据 #7: Accepted, time = 15 ms, mem = 20224 KiB, score = 5
测试数据 #8: Accepted, time = 15 ms, mem = 20224 KiB, score = 5
测试数据 #9: Accepted, time = 31 ms, mem = 20224 KiB, score = 5
测试数据 #10: Accepted, time = 15 ms, mem = 20224 KiB, score = 5
测试数据 #11: Accepted, time = 31 ms, mem = 20224 KiB, score = 5
测试数据 #12: Accepted, time = 31 ms, mem = 20220 KiB, score = 5
测试数据 #13: Accepted, time = 62 ms, mem = 20224 KiB, score = 5
测试数据 #14: Accepted, time = 62 ms, mem = 20220 KiB, score = 5
测试数据 #15: Accepted, time = 15 ms, mem = 20220 KiB, score = 5
测试数据 #16: Accepted, time = 31 ms, mem = 20224 KiB, score = 5
测试数据 #17: Accepted, time = 62 ms, mem = 20224 KiB, score = 5
测试数据 #18: Accepted, time = 93 ms, mem = 20220 KiB, score = 5
测试数据 #19: Accepted, time = 78 ms, mem = 20224 KiB, score = 5
Accepted, time = 601 ms, mem = 20224 KiB, score = 100
代码
var
n,m,i,ans,j:longint;
a:array[1..5000]of longint;
f:array[0..1000,0..5000]of longint;
procedure init;
begin
readln(m,n);
for i:=n downto 1 do read(a[i]);

for i:=1 to m do
for j:=1 to n do
f[i,j]:=maxlongint;
end;

function min(aa,bb:longint):longint;
begin
if aa<bb then exit(aa) else exit(bb);
end;

procedure dp;
begin
for i:=1 to m do
for j:=i*3 to n do
f[i,j]:=min(f[i,j-1],f[i-1,j-2]+sqr(a[j]-a[j-1]));
end;

procedure print;
begin
writeln(f[m,n]);
end;
begin
init;
dp;
print;
end.

70题纪念

= =mle。。一下午第5次= =