动态规划问题,一开始看到每天要买的糖果数还不一样,而且每个糖果还有他自己不同的价格。直接就想到了状压DP。 但本题要求花费最小,而对于某一天买k个糖果来说花费最小其实就是从价格低的糖果来买就行了。那么某一天如何选糖果的问题就这样简答的解决了。 那么状态数组为:dp[i][j]。i代表天数,j代表第到i天一共买j个糖果。值代表花费。 状态转移方程为:dp[i][j] = d[i-1][j-k]+cost(i, k)+pow(k,2);。 表示到某天一共买了j个糖果,取决于这天买了k个糖果,那么上一天就需要一共买了i-k个糖果。cost是计算这天买了k个糖果的最小花费是多少...