分类： 算法

这一题我就用的动态规划：f[l]=max(f[l], f[l – num[i]]); f[0] = 1; l是总面额，i是第num[i]个邮票的面值，但是超时，没想到别的算法，怎么办？找地方剪枝，见了三处就AC了，这效果立竿见影啊！后来到网上看了下，还有更快的方法，我是三重循环，它是二重循环，用f来记录当前使用的邮票总数（这种方法到别出去吧~- –）

这个题目其实算法还是比较简单，关键是怎么保存这些数字，其实啊，最好的保存方法就是二进制，且增加前缀1，比如0就是二进制10即十进制2，想必聪明的你要问为什么需要前缀1了，为什么呢？如果不要的话那么0和00都是二进制的0，怎么区分呢？所以用前缀1，那么最大的话也就是12位的1加一个前缀1，2^13=8192，接下来自己想想吧。

这个题目用数组来记录纸的每一个颜色是不可能的，无论是时间上还是空间上都无法忍受，就只能用具体的矩形来表示了，比如底纸，就是一张(0, 0, a, b, 1)的底纸，代表起始坐标是(0, 0)末坐标是(a, b)颜色是1，将它加入数组作为第一个元素，当添加进了一个新的矩形的时候，将数组所有的元素都和这个新的矩形比较，如果该元素被盖住了，就把数组中的那个元素拆分成几个没有被盖住的元素。 其实描述的很笼统，代码明天加入吧，在Ubuntu里面，现在不想切换过去了。 代码如下: de lang="c">/ ID: yylogoo1 PROG: rect1 LANG: C / #include struct paper{ int x1, y1; int x2, y2; int c; }; struct paper pa[4001]; int len; int stack[4000]; int top; int pop(void) { if(top == 0){ return len++; } return stack[–top]; } void push(int k) { stack[top++] = k; } void add(struct paper t) { int k; k = pop(); pa[k] = t; } void del(int k) { pa[k].x1 = -1; push(k); } void deal(struct paper new, int old_n) { struct paper old = pa[old_n], t; if(new.x1 <= old.x2 || old.x1 <= new.x2){ return ; } if(new.y1 <= old.y2 || old.y1 <= new.y2){ return ; } del(old_n); if(new.x1 = old.x2 && new.y2 <= old.y2){ return ; } if(old.x1 new.x2){ t = old; t.x1 = new.x2; add(t); old.x2 = new.x2; } if(old.y2 < new.y2){ t = old; t.y1 = new.y2; add(t); old.y2 = new.y2; } } int color[2501]; int main(void) { int n; int i, j; int a, b; struct paper t; freopen("rect1.in", "r", stdin); freopen("rect1.out", "w", stdout); scanf("%d%d%d", &a, &b, &n); add((struct paper){0, 0, a, b, 1}); for(i = 0; i = 0){ color[pa[i].c] += (pa[i].x2 – pa[i].x1) * (pa[i].y2 – pa[i].y1); } } for(i = 1; i <2500 i ifcolori> 0){ printf("%d %d\n", i, color[i]); } } return 0; }de>

这个题目属于什么算法呢？我才疏学浅不知道，反正就是用num来记录丑数，假设1为丑数，代码实现会简单些，那么丑数必定就等于另外一个丑数乘以一个素数，那么再一个个的按大小找到前n个丑数，就可以了。 时间的话大概是O(nm)，对每个素数都记录该和哪个丑数相乘start[i]，如果sub[i]（第i个素数）num[start[i]]是下一个丑数，那么start[i]就加一，如果sub[i]num[start[i]]和当前最大的丑数（就是才成为丑数的丑数）相等的话那start[i]也是要加一的，就这样循环。 / LANG: C ID: yylogoo1 PROG: humble / #include unsigned sub[100], num[100000]; int start[100]; int len; void add(int k) { num[len++] = k; } int main(void) { int i, j, k; int m, n; int min, in; freopen("humble.in", "r", stdin); freopen("humble.out", "w", stdout); scanf("%d%d", &m, &n); for(i = 0; i <m i scanfu subi add whilelen="n){" min="0xFFFFFFFF;" fori="0;" i m i ifsubi numstarti="= num[len" - starti ifmin> sub[i] num[start[i]]){ in = i; min = sub[i] * num[start[i]]; } } add(min); start[in]++; } printf("%u\n", num[n]); return 0; }

这题和第三章第一题一样，标准的无限01背包，直接把代码放进去就可以了，代码： / LANG: C ID: yylogoo1 PROG: inflate / #include int f[10001]; #define max(a, b) ((a)<(b)?(a):(b)) int main(void) { int m, n; int i, j; int a, b; freopen("inflate.in", "r", stdin); freopen("inflate.out", "w", stdout); scanf("%d%d", &m, &n); for(i = 0; i <n i scanfdd a b forj="b;" j="m;" j fj="max(f[j" - b a fj printfdn fm return code>