题解 P1782 【旅行商的背包】

· · 题解

此题是非常是坑啊。楼下说的好，AC的dalao发个题解方便大家（当然，给个AC的代码就更赞了）

理论上，单调队列远快于二进制做法，但是。。

先分析一下题目，前n个物品搞一个多重背包，后m个物品搞一个完全背包！仔细想想应该都能想到。

但是。此题，时限卡的非常紧。

我总结了几个不TLE的必备条件：

不要随手加memset；不要懒得写读优；可以养成没事就加inline和register的习惯；单调队列千万别用STL的deque，求最大值的时候也不要用STL的max，手写一个if；数组大小不要开的太大（这也费时间），差不多就好。

至于为什么单调队列跑不过二进制，这我也不太清楚，因为单调队列的效率分析本来就是在均摊意义下的Q_Q，这题可以使多重背包和完全背包的一个练手的极佳模板题。至于并不怎么懂多重背包的优化的童鞋，可以参观一下我的blog，里面稍稍详细的总结了一下：http://blog.csdn.net/no1\_terminator/article/details/51896966

参考代码【我良心吧？】

#include<cstdio>
#include<algorithm>
#define re register
using namespace std;
const int N=1e4+1;
int n,m,c;
int q[N],f[N],dp[N];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
int main()
{
    n=read(),m=read(),c=read();
    for(re int i=0;i<n;i++)
      for(re int v=read(),w=read(),d=read(),j=0;j<v;j++)
        for(re int h=0,t=0,k=0;k*v+j<=c;k++)
        {
            re int x=dp[k*v+j]-k*w;
            while(h!=t && x>f[t-1])t--;
            q[t]=k;f[t++]=x;
            if(q[h]+d<k)h++;
            dp[k*v+j]=f[h]+k*w;
        }
    for(re int i=0;i<m;i++)
      for(re int v=read(),w=read(),d=read(),j=c;j>=0;j--)
        for(re int k=0;k<=j;k++)
          if (dp[j-k]+(v*k+w)*k+d>dp[j])dp[j]=dp[j-k]+(v*k+w)*k+d;
    printf("%d",dp[c]);
    return 0;
}

最后，Orz一下最小面的dalao，他的单调队列写的确实漂亮，你们看了我的博客就知道差距了，学到了。