首页 > 代码库 > POJ 1742 Coins 多重背包单调队列优化

POJ 1742 Coins 多重背包单调队列优化

2024-07-16 02:47:49   220人阅读

http://poj.org/problem?id=1742

题意：

很多硬币，有价值和数量，给出一个上限，问上限内有多少种钱数可以由这些硬币组成。

分析：

好像是楼教主男人八题之一。然后学多重背包单调队列优化时看了别人的程序。。所以后来写了就1A了=。=

前一篇小小总结了一下多重背包单调队列优化(http://www.cnblogs.com/james47/p/3894772.html)，这里就不写了。

 

 1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4  5 int n, m, head, tail; 6 int a[150], c[150]; 7 int q[(int)1e5+100]; 8 bool dp[(int)1e5+100]; 9 int main()10 {11     while(scanf("%d %d", &n, &m) && (n+m))12     {13         for (int i = 0; i < n; i++)14             scanf("%d", a+i);15         for (int i = 0; i < n; i++)16             scanf("%d", c+i);17         memset(dp, 0, sizeof(dp));18         dp[0] = true;19         for (int i = 0; i < n; i++){20             int maxl = a[i] * c[i];21             if (c[i] == 1){22                 for (int j = m; j >= a[i]; j--)23                     if (dp[j - a[i]]) dp[j] = true; 24             }25             else if (m <= maxl){26                 for (int j = a[i]; j <= m; j++)27                     if (dp[j - a[i]]) dp[j] = true; 28             }29             else for (int j = 0; j < a[i]; j++){　　　　　　　　　　　　　　　//循环a[i]的同余类30                 head = tail = 0;31                 for (int k = j; k <= m; k += a[i]){32                     while (head != tail && k - q[head] > maxl) head++; //这题单调队列元素优劣性只取决于位置33                     if (!dp[k]){　　　　　　//只需踢掉前面已经超出长度的，即第i个硬币全用了也不能由它转移到当前值k34                         if (head != tail) //单调队列里有元素，可以被他们优化35                             dp[k] = true;36                     }37                     else q[tail++] = k;　　//dp[k]为真，可以优化后面的值，放入队列38                 }39             }40         }41         int ans = 0;42         for (int i = 1; i <= m; i ++)43             if (dp[i]) ans ++;44         printf("%d\n", ans);45     }46     return 0;47 }

 


联系
我们