Codeforces 939F.Cutlet-단조로운 대기열 최적화 dp

전송문

제목:

2∗n의 시간이 있으면 양면의 고기를 굽고 k개의 뒤집을 수 있는 구간 [li,ri] [l i,r i]를 줄 수 있다. 구간에서 임의로 뒤집을 수 있다. 구간이 서로 교차하지 않도록 합법적인 방안이 있는지 물어보면 양면이 딱 n분만 굽는다. 그리고 최소 뒤집기 횟수 n<=100000,k<=100을 구한다.

Solution：

수수하다
f[i][j]f[i][j]는 전 i초, 현재 구우지 않은 면은 j초 구워졌고, 필요한 최단 회전 횟수
이동 f[i][j]=f[i-3-1][j], f[i][j]=f[i-3-1] [i-3 j]+1 f[i] [j] = f[i-1] [j], f[i] [j] = f[i-3 1] [i-3 j] + 1
그러나 이것은 O(n2)O(n2)의 것이므로 최적화가 필요하다
두 번째 이동은 이 k구간에서만 발생하는 것을 알아차렸다
그러면 우리는 상태를 바꿀 수 있다.
f[i][j]f[i][j]는 전riri초, 현재 구우지 않은 면이 j초 구워졌으며, 필요한 최단 회전 횟수
동시에 우리는 각 구간의 고기가 최대 두 번 뒤집히는 것을 발견했다. 그러면 우리는 한 번 뒤집는 것과 두 번 뒤집는 것으로 나누어 토론할 수 있다
전이 즉 f[i] [j] = mink ≤ri 1lik=0(f[ii-4-1] [j: i] [j] [j] +2 f[i] [i] [i] [j] [j] + 2 [i] +2 [j] [j] = [i] = [i] [i] [i] [i] [i] [j] = [i] [i] [i] [i] [j] = [i] [i] [i] [j] [j] = [i] [i] [i] [i] [i] [j] = [i] [i] [i] [i] [ii i i i i = [[ii i 1] [[[i i i 1] [[i] [i] [[i] [[i] [i] [[이 + 1
이 두 개의 이동이 각각 단조성을 만족시키는 것을 발견하면 단조로운 대기열을 사용하여 최적화하면 된다
코드:

#include
#include
#define debug(x) l=l
using namespace std;
const int inf=1e9;
int n,m;
int f[110][100010];
int q[100010],h,t,l,r;
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) f[0][i]=1e9;
    f[0][0]=0;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        h=1,t=0;
        for (int j=0;j<=n;j++) f[i][j]=f[i-1][j];
        for (int j=0;j<=r;j++)
        {
            debug(j);
            if (j<=n)
            {
                while (h<=t&&f[i-1][j]<=f[i-1][q[t]])t--;
                q[++t]=j;
            }
            while (h<=t&&q[h]if (h<=t) debug(q[h]),debug(f[i][j]),f[i][j]=min(f[i][j],f[i-1][q[h]]+2),debug(f[i][j]);
        }
        h=1,t=0;
        for (int j=r;j>=0;j--)
        {
            debug(j); 
            if (r-j<=n)
            {
                while (h<=t&&f[i-1][r-j]<=f[i-1][q[t]])t--;
                q[++t]=r-j;
            }
            while (h<=t&&q[h]if (h<=t) debug(q[h]),debug(f[i][j]),f[i][j]=min(f[i][j],f[i-1][q[h]]+1),debug(f[i][j]);
        }
    }
    if (f[m][n]>=inf) printf("Hungry");
    else printf("Full
%d",f[m][n]);
}