P1004 [NOIP 2000 提高组] 方格取数
#走两次dp
如果只走一次，这题是非常经典的DP。但是要走两次，就变得非常有难度。
首先，可以简单地推广：要走两次，dp就存四个下标：
int[][][][] dp = new int[N][N][N][N];
|
我们只需要遍历所有可能，并且比较四种走法（同下、同右、一下一右），取最大值就可以了。
注意，一个数只能取一次，需要一个判断防止重复取数。
for (int i1 = 1; i1 < N; i1 += 1) {
for (int i2 = 1; i2 < N; i2 += 1) {
for (int j1 = 1; j1 < N; j1 += 1) {
for (int j2 = 1; j2 < N; j2 += 1) {
int step = map[i1][j1];
if (i2 != i1 && j2 != j1) step += map[i2][j2];
dp[i1][j1][i2][j2] =
Math.max(dp[i1-1][j1][i2-1][j2],
Math.max(dp[i1-1][j1][i2][j2-1],
Math.max(dp[i1][j1-1][i2-1][j2],
dp[i1][j1-1][i2][j2-1]))) + step;
}
}
}
}
System.out.println(dp[N-1][N-1][N-1][N-1]);
|
当然，4个循环时间复杂度太高了。我们可以用一个k == i1 + j1 == i2 + j2来减少一重循环。
这个k利用得很巧妙，因为每次要么向下走，要么向右走，所以k-1 == i-1 + j == i + j-1，全程使用k-1就能代表所有情况。
int[][][] dp = new int[2*N][N][N];
for (int k = 1; k < 2*N; k += 1) {
for (int i1 = 1; i1 < N; i1 += 1) {
for (int i2 = 1; i2 < N; i2 += 1) {
int j1 = k - i1, j2 = k - i2;
if (j1 < 0 || j1 >= N || j2 < 0 || j2 >= N) continue;
int step = map[i1][j1];
if (i1 != i2) step += map[i2][j2];
dp[k][i1][i2] = Math.max(dp[k-1][i1-1][i2-1], Math.max(dp[k-1][i1][i2],
Math.max(dp[k-1][i1-1][i2], dp[k-1][i1][i2-1]))) + step;
}
}
}
System.out.println(dp[2 * (N-1)][N-1][N-1]);
|
B3637 最长上升子序列
#单维dp
int[] dp = new int[N];
int max = 1;
for (int i = 0; i < N; i += 1) {
dp[i] = 1;
for (int j = 0; j < i; j += 1) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
if (dp[i] > max) {
max = dp[i];
}
}
System.out.println(max);
|
如何理解dp[i] = Math.max(dp[i], dp[j] + 1)?
这里dp[j]存储的是以j为结尾的LIS，而+1代表的是dp[i]自己。
我们通过计算出前面的所有dp[j]，最后只需要看对于每个nums[j]，它是否小于nums[i]，小于，就添加一个就可以了。
P2782 友好城市
#贪心 #LIS最优解法
友好城市可以转换为一个LIS问题：将北岸城市按照坐标顺序排序后，求北岸城市对应南岸城市的坐标LIS（南岸城市坐标必须递增，不递增就是交叉造桥），这就是不交叉情况下能够建筑的最多桥梁数。
传统的DP写法需要O(n2)的时间复杂度，会超时；下面介绍LIS的最优解法：贪心+二分。
贪心法求解LIS
对于一个序列sequence，遍历sequence[i]，维护一个上升序列数组，使其每个元素尽可能地小（这样整个序列就尽可能长），遍历结束，这个数组就是LIS。
具体的算法实现是：对于每个sequence[i]，查找它在贪心上升序列greedy中应该插入的位置（维持序列上升的位置），并替换原来的更大的元素，如果不存在更大的元素，在末尾追加该元素。最后，greedy就是LIS，greedy的长度就是能够建筑合法桥梁的最大值。
优化DP思路：交换状态与状态值
原来的DP是这样表示：
dp[i] 表示 末尾元素 为cities[i]的元素的LIS 长度
交换“末尾元素”与“长度”后：
greedy[i] 表示 长度 为i+1的IS的 末尾元素 的最小值
代码实现如下：
{
...
int[] greedy = new int[N];
int len = 0;
for (int i = 0; i < N; i += 1) {
int target = cities[i].target;
int index = lowerBound(greedy, len-1, target);
if (index == len) {
greedy[len++] = target;
} else {
greedy[index] = target;
}
}
System.out.println(len);
}
private static int lowerBound(int[] nums, int end, int target) {
int start = 0;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] >= target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
}
|
P1091 [NOIP 2004 提高组] 合唱队形
#双向LIS
合唱队形可以看成求两边LIS之和的最大值。此时总人数减去LIS之和的最大值，就是最少出列队员数。
这里要注意当前index+1的值才是正确的长度。len标记的是数组的总长度，但是index会动态更新寻找更小值并做替换。当index找到最小值时，后面的更大值是在index以前的，不属于当前下标i+1结尾的IS长度。
int[] gdUp = new int[N];
int lenUp = 0;
int[] lenUps = new int[N];
for (int i = 0; i < N; i += 1) {
int index = lowerBound(gdUp, lenUp-1, members[i]);
if (index == lenUp) {
gdUp[lenUp++] = members[i];
} else {
gdUp[index] = members[i];
}
lenUps[i] = index + 1;
}
int[] gdDown = new int[N];
int lenDown = 0;
int[] lenDowns = new int[N];
for (int i = N-1; i >= 0; i -= 1) {
int index = lowerBound(gdDown, lenDown-1, members[i]);
if (index == lenDown) {
gdDown[lenDown++] = members[i];
} else {
gdDown[index] = members[i];
}
lenDowns[i] = index + 1;
}
int max = 0;
for (int i = 0; i < N; i += 1) {
if (lenUps[i] + lenDowns[i] - 1 > max) {
max = lenUps[i] + lenDowns[i] - 1;
}
}
System.out.println(N - max);
|
P1020 [NOIP 1999 提高组] 导弹拦截
#最长不递增子序列
做这题各种WA让我非常confusing，仔细研究后发现是我没有理解导弹拦截的规则（可以拦截相等高度！），真所谓“失之毫厘，谬以千里”。原理其实很简单：
- 导弹系统可以拦截的最多导弹数，是一个最长不严格递减子序列（导弹高度不需要严格递减、可以相等），在题目要求的数据规模下，必须使用贪心+二分解法，转化为逆序求最长不严格递增子序列。
- 最少需要多少导弹拦截系统？一个系统只能拦截比前一个导弹高度更低的导弹，那么每出现一个比之前所有高度都更高的导弹，之前的系统都不能拦截。这就是LIS！
{
...
int[] gdDown = new int[N];
int maxMissile = 0;
for (int i = N-1; i >= 0; i -= 1) {
int index = upperBound(gdDown, maxMissile - 1, nums[i]);
if (index == maxMissile) {
gdDown[maxMissile++] = nums[i];
} else {
gdDown[index] = nums[i];
}
}
int[] gdUp = new int[N];
int numSystems = 0;
for (int i = 0; i < N; i += 1) {
int index = lowerBound(gdUp, numSystems - 1, nums[i]);
if (index == numSystems) {
gdUp[numSystems++] = nums[i];
} else {
gdUp[index] = nums[i];
}
}
System.out.println(maxMissile + "\n" + numSystems);
}
private static int upperBound(int[] nums, int end, int target) {
int start = 0;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] <= target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return start;
}
private static int lowerBound(int[] nums, int end, int target) {
int start = 0;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] >= target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
}
|
P1086 [NOIP 2004 普及组] 花生采摘
#模拟
这题是简单的模拟题，按照题目要求完成即可。不过有一些小细节需要注意：
- 数组下标从0开始，但是坐标不能为0，否则会计算错误。
代码使用了TreeMap来自动排序所有的花生植株，所以看起来不太直观。
{
...
findPeanut(map, M, N);
Map.Entry<Integer, Point> pre = peanuts.pollLastEntry();
if (2 * pre.getValue().x + 1 > K) {
System.out.println(0);
return;
}
K -= pre.getValue().x + 1;
int cnt = pre.getKey();
peanuts.remove(pre.getKey());
while (true) {
Map.Entry<Integer, Point> cur = peanuts.pollLastEntry();
if (cur == null) break;
int cost = Math.abs(pre.getValue().x - cur.getValue().x) +
Math.abs(pre.getValue().y - cur.getValue().y) + 1;
if (cost + cur.getValue().x > K) {
break;
}
K -= cost;
cnt += cur.getKey();
peanuts.remove(pre.getKey());
pre = cur;
}
System.out.println(cnt);
}
static TreeMap<Integer, Point> peanuts = new TreeMap<>();
private static void findPeanut(int[][] map, int M, int N) {
for (int i = 0; i < M; i += 1) {
for (int j = 0; j < N; j += 1) {
if (map[i][j] != 0) {
peanuts.put(map[i][j], new Point(i + 1, j + 1));
map[i][j] = 0;
}
}
}
}
|