自动搬运

查看原文

来自洛谷，原作者为

	QSWei **

搬运于2025-08-24 21:40:28，当前版本为作者最后更新于2017-08-06 16:25:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第一个点没有询问，只需要判断初始棋盘能否放下就行了。——直接把所有ci*ti加起来，判是否小于等于n即可.

第2到第8个点，只有一次询问。这个询问把棋盘分成了两段，我们考虑其中较短的那部分，就变成了一个背包问题——要在这部分中放置尽量多的物品，空间浪费得越少越好。（至于剩下的那部分，直接用物品总体积减去前面能够放入的物品体积，与剩余的空间进行比较即可。）每个战舰的价值即为它的长度，直接多重背包即可。第2、3个点直接是01背包，而后面的点由于c*n较大，朴素的背包会T，需要用单调队列优化得到O(cn)的算法.

第9到14个点，只有一种物品。我们二分答案，那么询问序列把棋盘分成了多个部分。假设某一段的长度为L，那么就可以放下L/size个物品。于是我们扫一遍就可以统计最多放置的物品数量，然后再根据要求二分下去即可。

第15到20个点，有两种物品。在二分的基础上（设分为了mid段），我们用f[i][j]表示考虑到前i段，恰好放置j种1号物品的前提下，可以放置的最多2号物品的数量。设第i段的长度为Li，转移方程为f[i][j]=max(f[i-1][j-k]+(Li-k*size1)/size2)，其中0<=k<=j且k*size1<=Li。那么f[mid][num1]就是当前状态可以放置的最多2号物品的数量，与要求进行比较，再二分即可。看上去这个方程是O(n^3)的，但实际上我们有k<=Li，因此对于确定的j，考虑所有的i，总共的决策数量不会超过sigma(Li)，即不会超过O(n)个。所以DP的复杂度为O(n^2)，整个算法的时间复杂度为O(n^2logq)，但远远达不到这个界，稍微优化一下就可以过了。

代码（c++）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 500010
int n,c,q,siz[maxn],num[maxn],od[maxn],que[maxn];
int f[maxn],sta[maxn],sta2[maxn],len[maxn],dp[2][4010];
bool cmp(const int &p,const int &q)
{
    return que[p]<que[q];
}
int main()
{
    int t; scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&c,&q);
        memset(f,0,sizeof(f));
        long long totsum=0;
        for(int i=1; i<=c; i++)
        {
            scanf("%d%d",&siz[i],&num[i]);
            totsum+=1ll*siz[i]*num[i];
        }
        for(int i=1; i<=q; i++)
        {
            od[i]=i;
            scanf("%d",&que[i]);
        }
        if(totsum>n) {printf("0\n"); continue;}
        if(q==0)
        {
            printf("-1\n");
        }
        else if(q==1)
        {
            int now=min(que[1]-1,n-que[1]);
            for(int i=1; i<=c; i++)
            {
                for(int j=0; j<siz[i]; j++)                 {
                    int ta=1,fr=1;
                    sta[1]=f[j]; sta2[1]=0;                    for(int k=1,e=siz[i]; e+j<=now; k++,e+=siz[i])                    {
                        int curf=f[e+j]-e;
                        while(ta<=fr && sta[fr]<=curf) fr--;
                        sta[++fr]=curf; sta2[fr]=k;
                        if(sta2[fr]-sta2[ta]>num[i]) ta++;
                        f[e+j]=sta[ta]+e;
                    }
                }
            }
            if(f[now]+max(que[1]-1,n-que[1])>=totsum)
                printf("-1\n");
            else printf("1\n");
        }
        else if(c==1)
        {
            sort(od+1,od+1+q,cmp);
            int l=0,r=q+1,mid=(l+r)>>1;
            while(l<r)
            {
                int ans=0,lst=0;
                for(int i=1; i<=q; i++)
                    if(od[i]<=mid)
                    {
                        ans+=(que[od[i]]-lst-1)/siz[1]*siz[1];
                        lst=que[od[i]];
                    }
                ans+=(n-lst)/siz[1]*siz[1];
                if(ans>=totsum) l=mid+1;
                else r=mid;
                mid=(l+r)>>1;
            }
            if(mid!=q+1) printf("%d\n",mid);
            else printf("-1\n");
        }
        else if(c==2)
        {
            sort(od+1,od+1+q,cmp);
            int l=0,r=q+1,mid=(l+r)>>1;
            while(l<r)
            {
                int tot=0,lst=0;
                for(int i=1; i<=q; i++)
                    if(od[i]<=mid)
                    {
                        len[++tot]=que[od[i]]-lst-1;
                        lst=que[od[i]];
                    }
                len[++tot]=n-lst;
                memset(dp,-0x3f,sizeof(dp));
                                dp[0][0]=0;
                for(int i=1; i<=tot; i++)
                    for(int j=0; j<=num[1]; j++)
                    {
                        for(int k=0,e=0; k<=j && e<=len[i]; k++,e+=siz[1]) //how many 1st items
                            dp[i&1][j]=max(dp[i&1][j],dp[(i&1)^1][j-k]+(len[i]-e)/siz[2]);
                    }
                                if(dp[tot&1][num[1]]>=num[2]) l=mid+1;
                else r=mid;
                mid=(l+r)>>1;
            }
            if(mid!=q+1) printf("%d\n",mid);
            else printf("-1\n");
        }
    }
    return 0;
}