단일 큐 최적화 DP-연습 문제 수집

전언

단조로운 대기열로 dp의 모델을 최적화할 수 있을 것 같아서 수필을 써서 만나는 비교적 대표적인 모델을 기록하고 업데이트를 계속한다.주로 수집과 정리, 총결산 업무를 한다.

레코드

0x01

POJ-1821 Fence는 입문에 적합한 문제로 전이 방정식을 쓴 후에 결정 변수의 수치 범위의 경계가 단조롭게 변화하고 가치를 분리한 후에도 단조롭다는 것을 쉽게 알 수 있다.

#include
#include
#include
#define dd(x) cout< P;
const int maxn=2e4+10,mod=1e9+7,INF=0x3f3f3f3f;
struct node
{
    int l,p,s;
}a[maxn];
bool cmp(node x,node y)
{
    return x.s=val(i,q[t]))
                --t;
            q[++t]=k;
        }
        for (int j=1;j<=n;++j)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if (j

0x02

HDU 3401 trade는 많은 블로그들이 단조로운 대기열 최적화 DP의 입문 문제로 여겨지지만 나는 이 문제에 고려해야 할 세부 사항이 매우 많고 간단하지 않다고 생각한다.정의 상태 f(i, j)는 i일째에 j 수량의 주식을 보유한 최대 수익이다. 이전하는 사고방식은 부작용, 구매와 판매의 세 가지 조작에 따라 이전하는 것이다.이전할 때 매도와 매수 작업에서 주식 수에 대한 매거는 단조로운 대열로 최적화된 다음에 우리는 매거진 며칠째 이전할 필요가 없다는 것을 알 수 있다. (어느 날 하지 않는 것을 허용하기 때문에 이런 조작의 존재는 분명히 f(i, j)>=f(i-1, j)가 있다. 즉, 일수의 증가는 수익을 크게 할 수 있을 뿐 더 나빠질 수 없다) 그러므로 직접 i-w-1로 이전하면 된다.따라서 총 복잡도는 제곱급, 즉 매거 i, j의 복잡도이다.자세한 내용은 코드 주석을 보십시오

#include
#define dd(x) cout< P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=2e3+10,INF=0x3f3f3f3f,mod=1e9+7;
int ap[maxn],bp[maxn],as[maxn],bs[maxn],f[maxn][maxn],q[maxn],h,t;
int main()
{   
    int T;
    cin>>T;
    while (T--)
    {
        int n,maxp,w;
        scanf("%d%d%d",&n,&maxp,&w);
        for (int i=1;i<=n;++i)
            scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
        for (int i=0;i<=n;++i)
            for (int j=0;j<=maxp;++j)
                f[i][j]=-INF;
        for (int i=1;i<=n;++i)
        {
            if (i<=w+1) //   ：    ｉ  ｗ+1 ，   ｊ     ，                ，      
            {
                for (int j=0;j<=maxp;++j)
                {
                    if (j<=as[i])
                        f[i][j]=-ap[i]*j;
                    f[i][j]=max(f[i][j],f[i-1][j]);
                }
            }
            else
            {
                //    
                for (int j=0;j<=maxp;++j)
                    f[i][j]=max(f[i][j],f[i-1][j]);
                //  
                h=t=0;
                q[0]=0;
                for (int j=1;j<=maxp;++j)
                {
                    while (h<=t&&j-q[h]>as[i])
                        ++h;
                    f[i][j]=max(f[i][j],f[i-w-1][q[h]]-(j-q[h])*ap[i]);
                    while (h<=t&&f[i-w-1][j]+j*ap[i]>=f[i-w-1][q[t]]+q[t]*ap[i])
                        --t;
                    q[++t]=j;
                }
                //  
                h=t=0;
                q[0]=maxp;
                for (int j=maxp-1;j>=0;--j)
                {
                    while (h<=t&&q[h]-j>bs[i])
                        ++h;
                    f[i][j]=max(f[i][j],f[i-w-1][q[h]]+(q[h]-j)*bp[i]);
                    while (h<=t&&f[i-w-1][j]+j*bp[i]>=f[i-w-1][q[t]]+q[t]*bp[i])
                        --t;
                    q[++t]=j;
                }
            }
        }
        int ans=-INF;
        for (int i=0;i<=maxp;++i)
            ans=max(ans,f[n][i]);
        printf("%d
",ans);
    }
    return 0;
}