POJ_1742_Coins
http://poj.org/problem?id=1742题意:现在有n种面值的货币,每种货币的面值为a,数量为c,求解能用这些货币组成多少种面值小于m的方案数.
北大变态的测试数据，套模板多重背包O(VN)复杂度的算法超时，据说单调队列优化也超了……
#include <iostream>#include <iomanip>#include <fstream>#include <sstream>#include <algorithm>#include <string>#include <set>#include <map>#include <utility>#include <queue>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <ctype.h>using namespace std;bool dp;int w, num, used, V, res;void pack (int cost, int amount) //简洁的背包，只适用于判断存在性{int j;for (j = cost; j <= V; j++){if (!dp && dp && used < amount) //使用次数不可超过amount{dp = true;used = used + 1; //该物品使用次数增加res++; //边背包边累计结果}}}int main(){int i, n;while (scanf ("%d%d", &n, &V) != EOF){if (!n && !V)break;for (i = 0; i < n; i++)scanf ("%d", w+i);for (i = 0; i < n; i++)scanf ("%d", num+i);memset (dp, false, sizeof(dp));dp = true;res = 0;for (i = 0; i < n; i++){memset (used, 0, sizeof(used)); //初始化存放使用次数pack (w, num);}printf ("%d\n", res);}return 0;}
页:
[1]