楼教主的“男人八题”之一，多重背包问题，che男让我用单调队列来做，可是我觉得单调队列太头疼，就搜了另外一种思路，然后自己写了一个。于是诡异的事情发生了，该题的Disscus里面也有一个我和的思路一模一样的代码，代码也几乎一模一样，连开的数组大小都是一样的，想说我不是抄的都没人信啊，郁闷。
这是Disscus里面的：
1 #include2 #include 3 #include 4 using namespace std; 5 6 bool can_pay[100005]; 7 int use_ai[100005]; 8 int Ai[105], Ci[105]; 9 int n, m, ans;10 11 int coins();12 13 int main()14 {15 int i;16 while(scanf("%d%d", &n, &m), n || m)17 {18 memset(can_pay, false, sizeof(can_pay));19 can_pay[0] = true;20 for(i = 0; i < n; ++i)21 scanf("%d", &Ai[i]);22 for(i = 0; i < n; ++i)23 scanf("%d", &Ci[i]);24 coins();25 }26 return 0;27 }28 29 int coins()30 {31 int i, j;32 ans = 0;33 for(i = 0; i < n; ++i)34 {35 memset(use_ai, 0, sizeof(use_ai));36 for(j = Ai[i]; j <= m; ++j)37 {38 if(!can_pay[j] && can_pay[j - Ai[i]] && use_ai[j - Ai[i]] < Ci[i])39 {40 can_pay[j] = true;41 use_ai[j] = use_ai[j - Ai[i]] + 1;42 ++ans;43 }44 }45 }46 printf("%d\n", ans);47 return 0;48 }
这是我的：
1 #include2 #include 3 int a[105],c[105]; 4 bool M[100005]; 5 int cnt[100005]; 6 int main() 7 { 8 int m,n,i,j,ans; 9 while(scanf("%d%d",&n,&m),m&&n)10 {11 for(i = 0; i < n; i++)12 scanf("%d",&a[i]);13 for(i = 0; i < n; i++)14 scanf("%d",&c[i]);15 M[0] = 1;16 ans = 0;17 for(i = 0; i < n; i++)18 {19 memset(cnt,0,sizeof(int) *m);20 for(j = 0; j <= m-a[i] && M[j]; j++)21 {22 if(cnt[j] >= c[i]) break;23 if(!M[j+a[i]])24 {25 M[j+a[i]] = 1;26 cnt[j+a[i]] = cnt[j]+1;27 ans++;28 }29 }30 }31 printf("%d\n",ans);32 memset(M,0,sizeof(bool ) *m);33 }34 return 0;35 }
为了证明我真的是自己写的，我把细节说一下，用Google搜“多重背包O(VN)”，打开第一条“曙光”的新浪博客，里面的思路就是我找到的了。不过我真的不是抄的，因为我的代码老是WA，这让我极度郁闷，几乎一模一样的代码，怎么我的就WA呢？坏就坏在这个“几乎”上，可以不夸张的说，两份代码只要有一个字节不一样，结果都可能天差地别。我一次又一次地提了十几回，终于找到了问题。
我的代码一共有3个问题。
1. 20行的“&&M[j]”，我有时候会把for(){ if() }的形式里if的条件直接加到for里面，事实证明，这不是个好习惯，这题要把这步放到for里面才行；
2. 22行的break，这样提前退出会漏掉一些情况；
3. 里面两个memset的规模，本来我觉得这样也没错，可是交上去就是WA，改成全部就行了，至于位置不重要，for的头和尾都行。
本来这题就是卡时间的，看到别人已经把复杂度缩到O(VN)了，还要绞尽脑汁地进行常数优化，而我的思路只要1000+ms，我很是得意，可是一看排行榜，一群300－ms的bug般的存在的大牛就在那里，不禁膜拜之。