这个DP气死我了.....写的时候脑子比较迟钝于是爆0了好几次，最后还是我旁边的AKIOI巨佬告诉我解法才会做。
我一开始设计的状态是f[i]表示i时刻正在休息，从1到i的最长休息时间。
然后经历了各种奇奇怪怪的事件，很多次接近崩溃......
先是按照旁边巨佬说的写了倒退，A了之后不甘心，跑去研究题解，然后在某个题解的评论上看到了一句让人醍醐灌顶的话：
可以建图解决问题
这样就豁然开朗了.....每个转移都是一条边，我们要求一个DAG上的最长链。所以正推倒推都是可以的。
然后我为了泄愤准备用三种方法A它，没想到爆了三次0......虐题不成反被虐>_<
随便放个代码吧
1 #include <cstdio> 2 #include <vector> 3 #include <cstring> 4 5 #define WWX_rank 1 6 7 const int N = 10010; 8 9 int a[N], f[N], op[N]; 10 std::vector<int> v[N]; 11 12 int main() { 13 int n, k; 14 scanf("%d%d", &n, &k); 15 for(int i = 1, x, y; i <= k; i++) { 16 scanf("%d%d", &x, &y); 17 v[x + y].push_back(x); 18 op[x] = 1; 19 } 20 21 memset(f, ~0x3f, sizeof(f)); 22 f[1] = 0; 23 for(int i = 2; i <= n + 1; i++) { 24 if(v[i].size()) { 25 for(int j = 0; j < v[i].size(); j++) { 26 f[i] = std::max(f[i], f[v[i][j]]); 27 } 28 } 29 if(!op[i - 1]) { 30 f[i] = std::max(f[i], f[i - 1] + 1); 31 } 32 //printf("%d %d \n", i, f[i]); 33 } 34 35 printf("%d", f[n + 1]); 36 return 0; 37 }
原文：https://www.cnblogs.com/huyufeifei/p/9918064.html
