链接:G-生蚝接柿子_"夜莺杯"武汉理工大学第四届新生程序设计竞赛 (nowcoder.com)
去年新生赛的一道题。
现在补一下。
分析
不难定义出状态dp[i][j]表示,到从下往上第i个柿子的时候,此时左手在j位置可以接到的最多柿子个数。
状态的转移也比较简单,dp[i][j] -> dp[i + 1][L ~ R],其中L, R是可以j到达的最远的位置。
当然从i - 1转移到i也可以,只需要计算出[i - m, i + m]的最大值,其中m是可以移动的最大距离,然后转移给i即可。
这里的转移时取大转移,只需要维护区间最大值即可。
代码
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 3e3 + 9; int n, v, x0, len, L = 3e3; int f[maxn], g[maxn]; struct Point { int x, y; }p[maxn]; void work(int m)// { memcpy(g, f, sizeof f);//f -> g, g = the last f memset(f, 0xcf, sizeof f);//f = -inf, 将所有点设为无法到达 deque<int> dq;//队列存放的是下标 for(int i = 1, j = 1;i <= L; ++ i)//枚举左端点, 维护[i - m, i + m]最大值 { while(j <= L && j <= i + m) { //调整位置,将队尾小的弹出 while(!dq.empty() && g[j] >= g[dq.back()])dq.pop_back(); dq.push_back(j ++); } //将不符合要求的队头弹出,如果下标不在[i - m, i + m]就不符合要求 while(dq.front() < i - m)dq.pop_front(); //队头维护的是[i - m, i + m]最大值,也就是f[i]的新值,单调队列保证dq不为空 f[i] = g[dq.front()]; } } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> v >> x0 >> len; for(int i = 1;i <= n; ++ i)cin >> p[i].x >> p[i].y; sort(p + 1,p + 1 + n, [](const Point &a, const Point &b) { return a.y < b.y; }); memset(f, 0xcf, sizeof f);//初始化为-inf,表示手到不了 f[x0] = 0;//手能到,能拿到0个柿子 int la = 0; for(int i = 1;i <= n; ++ i) { work((p[i].y - la) * v); //状态转移 for(int j = 1;j <= L; ++ j) if(j <= p[i].x && p[i].x <= j + len - 1)f[j] ++; la = p[i]. y; } int ans = 0; for(int i = 1;i <= L; ++ i)ans = max(ans, f[i]); cout << ans << '\n'; return 0; }
Comments NOTHING