CF939F Cutlet
2022/8/15 6:23:09
本文主要是介绍CF939F Cutlet,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
思路
先设 \(f_{i,j}\) 表示到第 \(i\) 秒时,正在煎某一面,另一面煎了 \(j\) 分钟
我们就有转移:
\[f_{i,j}=f_{i-1,j} \](不翻面的情况)
\[f_{i,j}=f_{i-1,i-j}+1 \](翻面,而且在区间内)
这是 \(O(n^2)\) 的,不能过
我们发现,显然一个区间内最多翻转两次,因为三次或以上可以合并成一或两次更优
我们考虑整个区间进行转移,\(f_{i,j}\) 的 \(i\) 表示区间,\(j\) 不变
因此有转移:
不翻转:
\[f_{i,j} = f_{i-1,j} \]翻转一次,翻转后到 \(r_i\) 煎了 \(k\) 秒:
\[f_{i, j}=\min\{f_{i - 1, r - j - k}\}+1 \]翻转两次,两次之间煎了 \(k\) 秒:
\[f_{i,j}=\min\{f_{i - 1, j - k}\} + 2 \]但这仍是 \(n^2m\) 的
看到 \(\min\),可以想到用单调队列进行转移
翻转一次的转移,弹出条件为 \(k>r-l\),即 \(p<l-j\)
翻转两次的转移,弹出条件为 \(k>r-l\),即 \(p<j+l-r\)
(这里的 \(p\) 即为转移点,注意翻转一次要用倒序)
代码
#include<iostream> #include<fstream> #include<algorithm> #include<cmath> #include<cstdlib> #include<cstring> #include<queue> #include<map> #include<set> #include<bitset> #define LL long long #define FOR(i, x, y) for(int i = (x); i <= (y); i++) #define ROF(i, x, y) for(int i = (x); i >= (y); i--) #define PFOR(i, x) for(int i = he[x]; i; i = r[i].nxt) inline int reads() { int sign = 1, re = 0; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();} while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();} return sign * re; } #define inf 1061109567 int n, m, l, r, i, f[2][200005]; std::deque<int> q; signed main() { #ifndef ONLINE_JUDGE freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #endif n = reads(), m = reads(); memset(f[0] + 1, 63, sizeof(int) * (n << 1)); while(m--) { l = reads(), r = reads(), i = i ^ 1, q.clear(); memcpy(f[i], f[i ^ 1], sizeof(int) * ((n << 1) + 1)); ROF(j, r, 0) { while(!q.empty() && f[i ^ 1][r - j] <= f[i ^ 1][q.back()]) q.pop_back(); while(!q.empty() && q.front() < l - j) q.pop_front(); q.push_back(r - j); f[i][j] = std::min(f[i][j], f[i ^ 1][q.front()] + 1); } q.clear(); FOR(j, 0, r) { while(!q.empty() && f[i ^ 1][j] <= f[i ^ 1][q.back()]) q.pop_back(); while(!q.empty() && q.front() < j - r + l) q.pop_front(); q.push_back(j); f[i][j] = std::min(f[i][j], f[i ^ 1][q.front()] + 2); } } if(f[i][n] ^ inf) printf("Full\n%d", f[i][n]); else puts("Hungry"); return 0; }
这篇关于CF939F Cutlet的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享
- 2024-04-14shell 正则判断字符串内是否含有th-icode9专业技术文章分享