首页 > 代码库 > scau 17967 大师姐唱K的固有结界 分类暴力 + RMQ
scau 17967 大师姐唱K的固有结界 分类暴力 + RMQ
由于能放两次,那么分类,
1、连续使用,(这个直接O(n^2)暴力)
2、分开使用。
分开使用的话,首先暴力枚举,用T时间,能从第1个位置,唱到第几首歌,然后剩下的就是从pos + 1, n这个位置,用T时间,最多能省多少体力。这个可以预处理 + rmq搞了。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 1e3 + 20; int t[maxn]; int val[maxn]; int T, H, n; int mx[maxn]; int dp_max[maxn][20]; void init() { for (int i = 1; i <= n; ++i) { int tot = 0, useTime = 0; for (int j = i; j <= n; ++j) { useTime += t[j]; if (useTime > T) break; tot += val[j]; } mx[i] = tot; } for (int i = 1; i <= n; ++i) { dp_max[i][0] = mx[i]; } for (int j = 1; j < 20; ++j) { for (int i = 1; i + (1 << j) - 1 <= n; ++i) { dp_max[i][j] = max(dp_max[i][j - 1], dp_max[i + (1 << (j - 1))][j - 1]); } } } int ask(int be, int en) { if (be > en) return 0; int k = (int)log2(en - be + 1.0); return max(dp_max[be][k], dp_max[en - (1 << k) + 1][k]); } void work() { scanf("%d%d%d", &T, &H, &n); int hurt = 0; for (int i = 1; i <= n; ++i) { scanf("%d%d", &t[i], &val[i]); hurt += val[i]; } init(); int mxsave = 0, ans = 0; for (int i = 1; i <= n; ++i) { int useTime = 0; int tot = 0; for (int j = i; j <= n; ++j) { useTime += t[j]; if (useTime > 2 * T) { break; } tot += val[j]; } mxsave = max(mxsave, tot); } ans = H - (hurt - mxsave); for (int i = 1; i <= n; ++i) { int tot = 0, useTime = 0; for (int j = i; j <= n; ++j) { useTime += t[j]; if (useTime > T) break; tot += val[j]; int res = ask(j + 1, n); mxsave = max(mxsave, tot + res); } } ans = max(ans, H - (hurt - mxsave)); ans = max(ans, 0); cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
scau 17967 大师姐唱K的固有结界 分类暴力 + RMQ
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。