摘要: [状态] f[i]表示从0到i点最少踩到的石子数, stone[i]表示i点有无石子;
[方程] f[i] = max{f[i-j] + stone[i]} (S<=j<=T)
[初始化] f[0] = 0, 其他赋值为无限大.
阅读全文
摘要: 树形DP，需要记录方案，并注意空树的情况.
[状态]f[i][j]从结点i到j的最大加分值
[方程]f[i][j] = max{f[i][k-1]*f[k+1][j]+a[k]} (i<=k<=j)
实现方程的时候循环顺序非常关键:结点数由小到大循环.否则会出现需要的值未计算的情况.
记录方案可以用一个数组d[i][j]记录k，然后递归寻找方案并记录.
阅读全文
摘要: 题目中附件不超过2个，因而主附件存在4种不同的存取情况，可以转化为分组背包问题.
[状态]f[k][v]表示添加前k组物品，剩余空间为v时的最大值
[方程]f[k][v] = max{f[k-1][v], f[k-1][v-c[i]]+w[i]}
阅读全文
摘要: 和2000的方格取数如出一辙.数据加强了一点，如果是裸的四维dp可能会超时(80).所以需要优化.
阅读全文
摘要: 简单dp，难点在于状态的表示.
题目可以看做两人同时取数，这样就避免了后效性，可以用dp做了.
【状态】f[i][j][k][l]表示两人分别到(i,j)、(k,l)所取过的数的和.G[i][j]表示方格里的数.
【方程】f[i][j][k][l] = max{f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1]}+G[i][j]+(i==k&&j==l ? 0 : G[k][l])
阅读全文