传送门
动归，用f[i][j]表示到达第I列高度为j时最少需要飞的次数，容易想到最裸的转移：
f[i][j]=min(min(f[i1][jup[i1]*k]+k),f[i1][j+down[i1]])
但是会超时
考虑怎么优化k的循环，发现k可以从k1转移过来，从图上来理解就是比如k=2时，相当于可以先从i1列飞一次飞到i列的jup[i1]位置，然后再往上跳一次跳到i的j位置，也就是f[i][j]可以从f[i]
[jup[i1]]+1转移来，这里需要注意几个地方
1.由于f[i][jup[i1]]相当于是中转的位置，所以无论那个位置是不是管道都要做
2.要保证f[i][jup[i1]]可以充当中转，所以必须先做一次只飞不掉的，再做一次掉下来的，否则会出现f[i][jup[i1]]位置可能是从i1列掉下来得到的，此时不能充当中转
3.要特殊处理高度为m的情况（看题目）
——代码
1 #include <cstdio> 2 #include <iostream> 3 4 const int INF = 19260817, N = 10001, M = 1001; 5 int n, m, k, b, ans = INF, sum; 6 int x[N], y[N], l[N], h[N], f[2][M]; 7 8 inline int read() 9 16 17 inline int min(int x, int y) 18 21 22 int main() 23 33 for(i = 1; i <= k; i++) 34 39 for(i = 1; i <= n; i++) 40 60 if(b) sum++; 61 else break; 62 } } 64 if(i == n + 1) 65 69 else printf("0\n%d\n", sum); 70 return 0; 71 }View Code
上一篇：[TyvjP1313] [NOIP2010初赛]烽火传递（单调队列 + DP）
下一篇：[luoguP1972] [SDOI2009]HH的项链（莫队 || 树状数组 || 主席树）
DP
