一道ACM题--A. Cut Ribbon http://www.codeforces.com/problemset/pro...

发布网友发布时间：2024-09-29 11:27

共2个回答

热心网友时间：2024-09-29 14:21

把题目说一下。——望采纳~

热心网友时间：2024-09-29 14:25

这题是用动态规划做的：
dp[i]表示长度为i的ribbon可以分成的最大份数。
<初始状态> dp[0]=0，dp[i]==-1000000表示长度i不可分为a,b,c。
<状态转移> 若i可分，则(i-a),(i-b),(i-c)中至少有一个可分。
dp[i] = max{dp[i-a]+1,dp[i-b]+1,dp[i-c]+1}

从1推到n，dp[n]就是答案了

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com