[NOIP 2014] 飞扬的小鸟：需要一点小优化的DP

本文主要是介绍[NOIP 2014] 飞扬的小鸟：需要一点小优化的DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这不是水题？
啊，写完了。等等，可以连击？？！
连击也好处理。用同一列的更新自己就好。
啊，又快写完了。等等，我这样倒着推，又用的是滚动数组，好像难以确定游戏失败时最多飞越多少个管道间隙……
嗯，重写。WA，70分，挂成暴力DP了。让我来面向数据调试……
为了省一个循环，我竟然同时更新向上、向下……
改正。CE两次。咦，怎么还是70分？这次WA的测试点有所不同。
再次面向数据……高度为m时，只考虑了“1次越界”、“1+次正好”，而忽略了“连击越界”。
85分了！怎么和本机运行结果不一样？数组开小了1。
95分。这是什么鬼？
一天都在想这是怎么回事。第16个测试点，答案是“0 142”，我输出“0 141”。怎么会少1呢？
写个暴力吧。靠！我的暴力DP也输出“0 141”！
读了很多遍题，确认题意没搞错。
晚上，又写了个暴力，还是输出“0 141”。在数据和vfk的代码的帮助下，我发现找到的第一个无法通过的管道间隙是正确的。在那之前，有142个管道，但这一版暴力怎么返回141呢？
原来，我统计的是0~i-1有多少个管道间隙，还没更新i-1就break了。
那优化后的DP是哪里错的呢？我发现col变量计的是最后一个能通过的列，但是我写着写着就把它当成了第一个不能通过的列。一个等号引发的血案。
在AC之前，又WA一次。原因是我加了句if (col != i) break;，后面判无解没改，还是把now扫一遍。

下面是参考vfk的代码，借鉴了一些好的写法的实现。比如min_element这个函数。

想起LTY学长的《混分导论》里写道，想AC看吕教主的代码去。

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 10000, MAX_M = 1000, INF = 0x3f3f3f3f;
int n, m, u[MAX_N], d[MAX_N], l[MAX_N+1], h[MAX_N+1], f[2][MAX_M+1];inline bool in(int j, int i)
{return j < h[i] && j > l[i];
}int* dp(int& cnt)
{int* now = f[1], * pre = f[0], x, y;cnt = 0;for (int i = 1; i <= n; ++i) {swap(now, pre);for (int j = 1; j <= m; ++j) {x = j-u[i-1];now[j] = min(x > 0 ? now[x] : INF, in(x, i-1) ? pre[x] : INF) + 1;}for (int j = max(m-u[i-1], l[i-1])+1; j <= m; ++j)now[m] = min(now[m], min(now[j], j < h[i-1] ? pre[j] : INF) + 1);for (int j = 1; j <= m; ++j) {y = j+d[i-1];now[j] = min(now[j], in(y, i-1) ? pre[y] : INF);}bool flag = false;for (int j = l[i]+1; j < h[i]; ++j)flag = flag || now[j] < INF;if (!flag)break;if (h[i] <= m)++cnt;}return now;
}int main()
{int k;scanf("%d %d %d", &n, &m, &k);for (int i = 0; i <= n; ++i)h[i] = m+1;for (int i = 0; i < n; ++i)scanf("%d %d", &u[i], &d[i]);for (int i = 0; i < k; ++i) {int p, a, b;scanf("%d %d %d", &p, &a, &b);l[p] = a;h[p] = b;}int cnt, * ret = dp(cnt); if (cnt == k)printf("1\n%d\n", *min_element(ret+1, ret+m+1));elseprintf("0\n%d\n", cnt);return 0;
}