首页 > 代码库 > [luoguP1280] 尼克的任务（DP）
[luoguP1280] 尼克的任务（DP）
传送门
原本想着 f[i] 表示前 i 个任务的最优答案，但是不好转移
看了题解后，发现是 f[i] 表示前 i 分钟的最优解，看来还是不能死脑筋，思维得活跃，一个思路行不通就换一个思路。
把 f 数组置为 -INF，f[0] = 0
如果当前时间不是任务开始的时间，f[i] = max(f[i], f[i - 1] + 1)
如果当前时间是任务开始时间，f[i + b[j] - 1] = max(f[i + b[j] - 1], f[i - 1])
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 100001 5 #define max(x, y) ((x) > (y) ? (x) : (y)) 6 7 int n, m; 8 int a[N], b[N], f[N]; 9 10 inline int read()11 {12 int x = 0, f = 1;13 char ch = getchar();14 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;15 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;16 return x * f;17 }18 19 int main()20 {21 int i, j;22 n = read();23 m = read();24 memset(f, -127 / 3, sizeof(f));25 f[0] = 0;26 for(i = 1; i <= m; i++) a[i] = read(), b[i] = read();27 j = 1;28 for(i = 1; i <= n; i++)29 {30 if(a[j] ^ i) f[i] = max(f[i], f[i - 1] + 1);31 else while(a[j] == i)32 {33 f[i + b[j] - 1] = max(f[i + b[j] - 1], f[i - 1]);34 j++;35 }36 }37 printf("%d\n", f[n]);38 return 0;39 }
[luoguP1280] 尼克的任务（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。