#280. 橱窗布置
橱窗布置
说明
假设以最美观的方式布置花店的橱窗,有F束花,每束花的品种都不一样,同时,至少有同样数量的花瓶,被按顺序摆成一行,花瓶的位置是固定的,并从左到右,从1到V顺序编号,V是花瓶的数目,编号为1的花瓶在最左边,编号为V的花瓶在最右边,花束可以移动,并且每束花用1到F的整数惟一标识,标识花束的整数决定了花束在花瓶中列的顺序即如果i例如,假设杜鹃花的标识数为1,秋海棠的标识数为2,康乃馨的标识数为3,所有的花束在放人花瓶时必须保持其标识数的顺序,即:杜鹃花必须放在秋海棠左边的花瓶中,秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目,则多余的花瓶必须空,即每个花瓶中只能放一束花。
每一个花瓶的形状和颜色也不相同,因此,当各个花瓶中放人不同的花束时会产生不同的美学效果,并以美学值(一个整数)来表示,空置花瓶的美学值为0。在上述例子中,花瓶与花束的不同搭配所具有的美学值,可以用如下表格表示。
<img src=http://101.43.101.245:80/admin/../'data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAeQAAABvCAIAAACyzCQBAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAAA69SURBVHhe7V1bcuQ4DtzaY9gXsL/sCPf9T9Afnq+eC3iu0UMHZrBYvkSRAEhRWdHRUVWmSGQCTEEQi3r8/v37P/++/vjzr7eXJ/649xuA3dW/8Cw8uwEDMozD+4DovxugAgQwAAbAwMYMhBw6/INYb+xiQAMDYGAfBh5cBnk8HvvAAhIwAAbAwMUZkDXqAOXx+euLEL2/Pl8cGswHA2AADOzDAIsz3UqMM+tIy/fBnSAJVxIAu6V/4dkt3fqtVreZs1TniAQKNetdAxu4wAAY2IoBiPVW7gQYMAAGdmUAYr2rZ4ELDICBrRiAWG/lToABA2BgVwYg1gqe/fHjR9RL+k1oIL/MNlAwxb4LgE05hmft4055hCuGMcRaOQgq3f38+ZNCJPwf3tMb+fIzxX4kgIVn7aPMfISlwhhL9/r93Zgdky6XXizc/XY0HDm+5glgU5rhWeYEYdwwC080yS7dg1ifYLBdcLOxG+kdJ9elOa84AcbFujItx8FKZuoK2OItgG1hKVvMicgf9yyNohXJK3s2zWZGIjkr1t/rrulFtPLH7d/ogv34+GDG5PuIRvpT1Dh8jA6hbyr9nPXO4mAlnHHUAHs2PLKhOx7GLTPilKkX8uwpXGnjrBqjZt2XhegcRRlHegbOfqkz5LxeSmDnWWQ4MsDKSzFDot27nuhZiLWCt0tXeY11XgULHLtQBztytWiN2xSsVnFAiwR1sIoFEC2M8hSSDbzBOct3ldUNDh1CrEdZLXk3Cn3yIoUv/y/fjNrhcrw12KX0yw4sBcNSZykLsKthPEz2B+csJ928hkR3UkKsh/isJCPRVOTKBn3PfzXy6xCqwsHWYJea26ZgKRgGkzhFF5uCVbRTpSsjsA6lS4h1fwBkvU4z8FTSdKpxv7ljR1qDXV+p1T27iF6belZeUK5wcjIFOzbDjo+GWB9zVGqRrnNaSnH6geWONAW7Gm92YFcQrMi9dmAp2eRLyRWSEjuwDp6FWKtpWvY6SLrwUJIc/K2FVhFsWijUMlKrH0WwWibZ9QOwy85ZiLVd2Df1nBXo1S4em5A0NKrcxSLIFzpdHcLNYqHSB79WSDYPgbQ0qDiO/rSTc6d5Fj+KGVy+Hv3IhXrjX7XwLwuyv5pJfx0zbky2hzBbtHpOfysBsOmvP+BZrXiT/dwnjOkEGXGIn5u35A2Xb6P4O931uQDY9X3UZ+F9PIvHevVFCI4CA2AADMxnADXr+T6ABWAADICBQwYg1ocUoQEYAANgYD4DEOv5PoAFYAAMgIFDBh6fv76o0fvr82FrNAADYAAMgAEfBlic316ewohYDeJD++RR7nMb/TumH/+L6sm82w8PsPYcTxgBq0EmkI4hwQAYAAMqDKBmrUIjOgEDYAAM2DIAsbblF72DATAABlQYgFir0IhOwAAYAAO2DGiKdbq/ydl9eQ63g5FknO3clkj0DgbAABiwZEBTrNvtlBuPseYe7iDa3j9aggEwAAY2Y0Bz6V6qtiX9ld/T+yhN5q0jG9Pnjq0mseZps1BmOPAsPHt1BrJL93TEuiK1WRnNirUU6PSo9jNBo5+cpzSxL19h/8NGU8eb+YCVGCW60vfjuLI9+IAtDe3sZX+wdW+a2mPauXRcaSDGbj15DddZdzy8J7vZfCWPjrLvK9ZM5Nbh1s420sFKtxTf/OKwLn3vb6HPiNEexD6Duo2yvTcDwDSvInoZuxvb0UAmNWspxFlR5oezRc8Q6qhmzCIO44IBMBAxUJK5CxFF59rUYJlrz8q0dMogARsnxVJwKzVrSQdlzTJ3PiyDcM/dKbbbJVUa0P7O9gebHdHHDJ9RKhUYt4tlTvdmqaGkmt6bkm/aeb0M4jY0Z/HhTSQUypl1equwFEbyycfcJvulPBNEvXUr9azgvsm4aWTT1aX/WcqCcMISvXggWSi4aKZZBxghlSUCC7aX6pOZmWKVjlhL0WwsZaTlkex6PlLqw7uUU7jrGHQbwapgz2Kkq8uLilcEtvSUS0qFNjghVQBmlbpjIlzxkOmnYR2xbhToqPQhC9alKnZWqank0jHoFUPkWjbXz0bb6PW1nKJubanGRSdjSj/VB53e4fTTsI5Yd/AYZdYyrY40XX6kZpDpDsIdDinNYYehFxliS5GKuK1cOZGc7XF5sUhESTOmiXVUnpaZdYWmaPUItWz84cyC7O9kUjSH7yBbO7mvEQu83EiURbNpYm0BBn3OZUDemGJLqPTBr+nXkqYU3QFs1svE6gZlEK7hRMWcFTyrtnSPMtz6apDoN4ql1X6hq8Ole1FC3VEYucO9PhYmgDXV6Imdw7MTybcbmk57UWajKdZ2plv0jCi3YHWFPuHZFbxgYcN9PJsVa5RBLIIKfYIBMAAGlBmAWCsTiu7AABgAAxYMQKwtWEWfYAAMgAFlBiDWyoSiOzAABsCABQOPz19f1O/767PFAOgTDIABMAAGOhhgcX57eQqHYzVIB4fXO+Q+t9G/Y3qXHaNa4gxgW1i6XBusBrmcy2AwGAADYOAfBlCzRiiAATAABi7AAMT6Ak6CiWAADIABiDViAAyAATBwAQb0xZp2MWXoLVvitbQ51eEFiIeJYAAMgIEzDKiJNW9Ind3FNDLplDqHY0vtz/Zzhhm0BQNgAAwsxICaWLdoNONON+eLnukVqXB2Mz88hWChOIIpYAAMGDOgvM5aCijvmEr7l/Y9SrExd15/i9R0M37PnZ19VuNKjPHujo5rn33A1iemmw3TB8quCDZSLR+wpTCuhLc6XsMtUlNJpVyY/5dinRX0CG2083Wdi74U28fxbLnzcBFjDqNHQ/BHDnG3k5MD2MPJ6WaDw0AVD0ovO/jXB6wEUgJobYmhWMu7f+kTBtLMOpLXlhw8m2J3JNSz1NPau9MTvZJYk2Ge8D3HytK+X7KZ9WDd44fns44GDp6t5BxZEe9A0XJINoTUataUO2dVO62BZEW2/pSZ0EnpCegt4BdpE3xAr0XsUTTDIbFStNauKwdBsTMePZfC2FOpS17QrFmXHtOVleb2Z4CR6Rtk1gEFu9x5Sk8fztMA67Gy51ryrHNZwPOSJWV1y8xaCmUWspzFdue2/MUZPTeeRYQ/nn3z8fERDpH/px9ln9SSXvJ9+jGyJGp81k6Jt/vY8QPJ5W4vz+GyY003wIdqhumGd+JA0dAOljgM0aIPDmbQaSAKWs0yCJ9nDkvJ6T3GUu6cXdJXX+dnd7pDz4cMWGe1hwZMb8Blrl3rXdMZdjCgHsZBQ6dUMnXEum89RkR6tmYt69ShPZ0G+H/+q4P/BoeY4t1Bm88eDqVO87KzHKL9dAayYbzC/NWsWVN2nF11V/q+lFCzIpPnqGAdrSqRX3Y42FlZ/At8khMHsHWADgYwXs+xSoHnZsPcgZxr9A5gS2HsPH+zNWudzLpDK2XNJF3mIRWfhD4trdCXVBIZMcDnWLp04hffJPAZ3WcUCVBKJ0XefcoCm+GtFHY4qneK52wYrzB/rTLrtDDSUippSZZb+mnRJoezdIsZPm0A1odn/1HgWX/OHUbMZtbKYu0AQ2sIRLkWk6v1A8+u5hEte+7j2UXLIFqORD9gAAyAgY0ZmF+z3phcQAMDYAAMaDEAsdZiEv2AATAABgwZgFgbkouuwQAYAANaDDw+f31RX++vz1qdoh8wAAbAABgYZIDF+e3lKXSF1SCDfF7j8PvcRv+OaccHHUx3P8BOd4GFAVgNYsEq+gQDYAAMeDCAmrUHyxgDDIABMDDIAMR6kEAcDgbAABjwYABi7cEyxgADYAAMDDJgJdbqmytFHcotrQcpwOFgAAyAgfUZMFwNUtlxqS7lcoO90tO8uPPufZ1wG3396OyzEJ7t4239o+7jWfONnA6z6XSb0/bN+eo7Yh8+myYNxPs4PmAH2PWVqM9CeLaPt8WP8hDrKCk+1NBIrLNpcnQO4EcQMN2Ho2Qd4x/l5AB6Rfv/Whtj3X/EsESaxWs6VZzBzo0uf7D1ME5jW9HXPmAnAmSunNZZczU5DCzfj/hMPs1LanSfTI9Y0n0sxRm/OCDCm1TaukdZ58DoWZ/rGAZLRhgohTFfvc16PuEIKHnsygD1bzDK5yJmn/BSovWwxi1TbH5GzIX0OgucRE0r1NDPCgxsefatEytz3qvr9eGl0iyAmjcYR2rW6bHZZzkyj1e/wRhd0Flf31n3n5ZBZEA7n42cwZaw+6BeASyn1fIq3gK+P1ge0X/CpgUlZbHO1qxLKXM9lZaPx62cBrozawvHZ1OqNGrToS2MSS/u3LLOqOJmjS4rl3ZgK14uzW1TY9RlsSOMfbRsYiD5AKzXrPXFurTYLo3XFrE+ddSpKeHs+HrSYW2Mdf/t18infNTXeCLYPcS6hfa6eBm5wKjbw7qH26WDt1inlYrwTWmZRykvllWOltDpyK89HX94eWhtjHX/EGtiIM1J1dNe58uIFiFz0zK3MD689rW2JLo2JS/o32CUmTW9P6vUMj6ytyv5vqX8a4umz21j7eC56OTo2evodcyzs4TXwIQhdr11vH0YLwtQTaxZkWmdBs0Het+R9kbTiUU/fWM38XR7Ti8bdftHb2DAgYFSGMv7ycuKXQs/KwNUE2smIlJnqd2lNqk0y6Ug8jTAqTSvvKal3C1umN4mxAG/2Bj6hi4kt0lIaeryy7oUMN2zkQH7OTS6bErDmK4k6Puruzs7T1cAqHODMV1IRwIqNZc/VhaHcD6eTr/2+5aNU3eDqGpESmeCq08hgM0yAM+2B8aFWtL5Pv6dM3/O/vlC8M6aiig/y9hV2sOzV/HUWTvv49msGuuXQc46AO3BABgAA2DgkAGI9SFFaAAGwAAYmM8AxHq+D2ABGAADYOCQgfgG4+EBaAAGwAAYAAMODMQ3GD9/fdGo76/PDsNjCDAABsAAGGhhgMX57eUptP+/FV1//PkXfXuHF8Du6mV4Fp7dgIE0jFGz3sCtgAAGwMD+DECs9/cxEIIBMLABA49QFrlP6WMDhwECGAAD92QAmfU9/Q7UYAAMXIwBiPXFHAZzwQAYuCcDfwNESN9bDUV1ngAAAABJRU5ErkJggg=='/><br>根据表格,杜鹃花放在花瓶2中,会显得非常好看,但若放在花瓶4中则显得很难看。<br>假设条件:<br>1≤F≤100,其中 F 为花束的数量,花束编号从 1 至 F 。<br>F≤V≤100,其中 V 是花瓶的数量。<br>−50≤Aij≤50,其中 Aij 是花束 i 在花瓶 j 中的美学值。<br>输入整数F,V和矩阵(Aij),输出最大美学值和每束花摆放在各个花瓶中的花瓶编号。<br><br> <h2>输入格式</h2> 第一行包含两个数:F,V。 <br>随后的F行中,每行包含V个整数,Aij 即为输入文件中第(i+1)行中的第j个数。 <h2>输出格式</h2> 第一行是程序所产生摆放方式的美学值。 <br>第二行必须用F个数表示摆放方式,即该行的第K个数表示花束K所在的花瓶的编号。 <pre><code class="language-input1">3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20</code></pre><pre><code class="language-output1">53 2 4 5</code></pre> <h2>来源</h2> 第九章_动态规划_第三节_动态规划经典问题