牛客的题
有一种情况,就是k小于n时候,1到不了k,那就把dp全设置成负无穷(-1不行)这样就用不到了
#include<iostream> #include<cstring> #include<queue> #include<algorithm> #include<cstdio> using namespace std; typedef long long ll; const int maxn = 1e5 + 7; const ll INF = 1e17 + 7; ll dp[maxn]; ll map[220][220]; struct Node { int t, p, val; }que[maxn]; bool bml(Node a, Node b) { return a.t < b.t; } int main() { int n, m, q; scanf("%d%d", &n, &m); for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { if (i == j) map[i][j] = 0; else map[i][j] = INF; } } int x, y; for (int i = 0; i < m; i++) { scanf("%d %d", &x, &y); map[x][y] = map[y][x] = 1; } for (int k = 1; k <= n; k++) { for(int i=1;i<=n;i++){ for (int j = 1; j <= n; j ++ ) { map[i][j] = min(map[i][j], map[i][k] + map[k][j]); } } } scanf("%d", &q); for (int i = 1; i <= q; i++) { scanf("%d%d%d", &que[i].t, &que[i].p, &que[i].val); } sort(que + 1, que + 1 + q, bml); for (int i = 0; i <= q; i++) dp[i] = -INF; que[0].p = 1; dp[0] = 0; ll ans = 0; for (int i = 1; i <= q; i++) { if (i > n) dp[i] = max(dp[i], dp[i - n] + que[i].val); for (int j = 1; j <= n && i - j >= 0; j++) { if (que[i - j].t + map[que[i].p][que[i - j].p] <= que[i].t) { dp[i] = max(dp[i], dp[i - j] + que[i].val); } } ans = max(ans, dp[i]); } printf("%lld ", ans); return 0; }