[luoguP2948] [USACO09OPEN]滑雪课Ski Lessons（DP）

传送门

f[i][j]表示i时刻能力值为j的最大滑雪数

显然f[0][1]=0,开始搜索

三种转移：

①美美的喝上一杯**：f[i+1][j]=max(f[i+1][j],f[i][j])

②滑雪，f[i+当前能力值所能滑雪最短时间][j]=max(f[i+当前能力值所能滑雪最短时间][j],f[i][j])

③上课，对于所有i时刻开始的课，f[i+该课所需时间][该课达到能力值]=max(f[i+该课所需时间][该课达到能力值],f[i][j])

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 100001 #define max(x, y) ((x) > (y) ? (x) : (y)) #define min(x, y) ((x) < (y) ? (x) : (y)) int t, s, n, ans, mx = 1; int val[N], f[N][101]; //val[i]表示滑雪能力为i时一次滑雪的最低耗时 //f[i][j]表示时间为i，滑雪能力为j所能滑的最多次数 struct ovo q[N]; struct qwq p[N]; inline int read() inline bool cmp(qwq x, qwq y) int main() for(i = 1; i <= n; i++) std::sort(p + 1, p + n + 1, cmp); j = 1; val[0] = 1e9; for(i = 1; i <= 100; i++) memset(f, 1, sizeof(f)); f[0][1] = 0; for(i = 0; i <= t; i++) } for(j = 1; j <= s; j++) if(mx != 1 && i >= q[j].m) f[i + q[j].l][q[j].a] = max(f[i + q[j].l][q[j].a], mx); } for(i = 1; i <= 100; i++) ans = max(ans, f[t][i]); printf("%d\n", ans); return 0; }

　　

上一篇：[luoguP2129] L国的战斗续之多路出击（模拟 || 矩阵）

下一篇：[luoguP1227] [JSOI2008]完美的对称（sort）

---

DP