SRM 208 DIV1 的level 3，题意是给一个张网，每个给子里有一定量的苹果，求然后有三个人从左上角走到右下角，每个人走过一个格子的时候就会把当前格子里的苹果都带走，问三个人能拿到的最多的苹果是多少。
很显然的一个解法dp，dp[step][i][j][k]，意义是走完step步，第一个人在(i,step-i)，第二个人在(j,step-j)，第三人在(k,step-k)的时候能拿到的最多苹果是多少。
这题还有另一种解法，是要观察出一个性质，就是三条路径除了第一行和最后一行，路径不会相交，就是说可以理解成从第一行连到最后一行的三条路，路径不相交，相交肯定不是最优的，这个比较容易证明。然后是dp的时候怎么能体现出这个三条路径不相交的性质来。dp[row][i][j][k]为第row行，当前三条路径终点在(row,i)，(row,j)，(row,k)三个点时能拿到的最多苹果 ...
1、任何的01背包，都可以把价值V和容量W互换，就是说有两种方法可以解背包，比如将n个物品放入容量为W的背包，问能获得的最大价值。可以转化为，将n个物品放入容量为V（V为所有物品的价值总和）的背包，能获得的最小价值（对应于原问题中的最小重量）是多少。所以，当某个方向的问题不可解时（比如状态太多，或者状态下标要用浮点数表示什么的）就可以将其用另一个方向做，典型的问题是hdu2955抢银行。
2、有的时候我习惯用dp值为-1代表某个状态不可达，因为有些时候怕如果赋值为正负无穷的话会运算越界，但是如果设置不合法dp值为-1的话，一定要确保正常的dp值不能为-1。
3、打印解路径。可以用两个一维数组打印（一个数组是dp数组，另一个是决策数组s，s[i]记录dp[j]是怎么转移来的），这个时候需要背包是恰好装满时候的背包，如果是可以不装满的背包，无法用两个一维数组来打印解路径，需要至少用一个二维数组，但是其实任何不装满的背包都可以按照装满背包的方法解，最后再检查一遍所有的合法值就行了。
Page 1 / 1