Shilcare

Knight Moves

Time Limit: 1000MS
 
Memory Limit: 30000K

Total Submissions: 12076
 
Accepted: 5287

Description

Background
Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position...

这道题是经典题目“石子合并”的变形。同样也是用动态规划来解。

用dp[i, j]表示从第 i 堆开始的 j 堆混合物合并所释放的最少烟雾量，sum[i, k]表示从第 i 堆开始的 j 堆

混合物合并后的颜色。显然有状态转移方程：

dp[i, j] = min{dp[i, k] + dp[i + k, j - k] + sum[i, k] * sum[i + k, j - k]} &nbs...

题目大意是一个人突然得到了一大笔钱，但是一时不知道怎么花，就想买债券。

现在有几种债券，分别有不同的投资成本和收益。问在m年后最多能得到多少钱。

思路：把债券视为物品，第k年初的钱视为背包容量。显然转化为完全背包问题。

不过这题要注意的是要先进行状态压缩，否则会超出内存限制。

因为债券成本都是1000的倍数，显然可以先除以1000，收益不用处理。