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;
}