【Description】
为了纪念9.11,大家决定重修双子塔. 材料是立方体的水晶{这么阔！}， 问对于给定的水晶，可否修起等高的 双子塔(高度<＝2000).
【Input】
第一个数字N(100000以内)代表水晶的个数.
接下来N行每行一个数(<1000),代表水晶体的边长.
【Output】
如果可以建成就输入高度，不能建则输出0.
【Sample Input】
4
11
11
11
11
【Sample Output】
22
【算法描述】
动态规划。
由于这道题目已经给出了相等的高度不会大于2000，所有可以用装箱问题的模型来做这个道题。
【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include <stdio.h> #include <string.h> int main() { int n, i, j, a[3000]; //a[i]存储是可以搭建的塔高为i时的方法种数。 int b[100001], sum = 0; scanf("%d", &n); for (i = 1; i <= n; i++) { scanf("%d", &b[i]); sum += b[i]; } memset(a, 0, sizeof(a)); sum = sum / 2; a[0] = 1; if (sum > 2000) sum = 2000; for (i = 1; i < n; i++)//对于每个立方体 { for (j = sum - b[i]; j >= 0; j--)//从后面往前面找已经存在的高度。 { if (a[j] >= 1) a[j + b[i]]++;//这里是与装箱问题不同的地方。 } } for (i = sum; i >= 0; i--) //找最大值 if (a[i] > 1) break; if (i <= 0)//特殊情况，比赛时就因为这里所以错了两次。切记切记！ printf("0\n"); else printf("%d\n", i); return 0; } |