题解 P2688 【大海战】
第一个点没有询问，只需要判断初始棋盘能否放下就行了。——直接把所有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;
}