[训练指南][单调队列][DP] 滑动窗口单调队列优化线性dp 输出格式坑 LA3983

我上次wa两个小时是什么时候???妈的这个题格式。。。提示一个PE能死啊我去

直接暴力dp很好想但是复杂度爆炸,经过转换后可以把i和j分离开,然后j的那一部分就成了独立的只跟j有关的,这时候就可以把他当成一个新的量,然后求的时候就是在weight(j+1,i)<c的条件下(可以发现这其实是一个滑动的窗口)求出使得wav最小的j,就很像基本的dp了,只不过求最小j的时候用单调队列优化了。


#include 
#include 
#include 
#include
#include
#include
#include
#include
#include
//#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;

struct wp
{
    int x,y,w;
}wps[maxn];

int dor[maxn],df[maxn],hd[maxn],d[maxn],tw[maxn];
int pst[maxn],f,r;//f==r means empty

void del(int x)
{
    if(x==pst[f])
        f++;
}

void ins(int x)
{
    r=upper_bound(pst+f,pst+r,x)-pst;//upper
    pst[r++]=x;
}

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int T,c,n,temp,left;
    scanf("%d",&T);
    while(T--)
    {
        memset(wps,0,sizeof(wps));
        f=r=0;
        scanf("%d%d",&c,&n);
        scanf("%d%d%d",&wps[1].x,&wps[1].y,&wps[1].w);
        dor[1]=wps[1].x+wps[1].y;
        tw[1]=wps[1].w;
        for (int i=2;i<=n;i++)
        {
            scanf("%d%d%d",&wps[i].x,&wps[i].y,&wps[i].w);
            tw[i]=tw[i-1]+wps[i].w;
            dor[i]=abs(wps[i].x)+abs(wps[i].y);
            df[i]=df[i-1]+abs(wps[i].x-wps[i-1].x)+abs(wps[i].y-wps[i-1].y);
        }
        left=0;
        ins(d[0]+dor[1]-df[1]);
        for (int i=1;i<=n;i++)
        {
            while(tw[i]-tw[left]>c)//error?
            {
                del(d[left]+dor[left+1]-df[left+1]);
                left++;
            }
            d[i]=pst[f]+dor[i]+df[i];
            ins(d[i]+dor[i+1]-df[i+1]);
        }
        printf("%d\n",d[n]);
        if(T)
            printf("\n");
    }
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据