首页 > ACM题库 > HDU-杭电 > hdu 2730 Painter-分治-[解题报告]C++
2014
02-14

hdu 2730 Painter-分治-[解题报告]C++

Painter

问题描述 :

The local toy store sells small fingerpainting kits with between three and twelve 50ml bottles of paint, each a different color. The paints are bright and fun to work with, and have the useful property that if you mix X ml each of any three different colors, you get X ml of gray. (The paints are thick and “airy”, almost like cake frosting, and when you mix them together the volume doesn’t increase, the paint just gets more dense.) None of the individual colors are gray; the only way to get gray is by mixing exactly three distinct colors, but it doesn’t matter which three. Your friend Emily is an elementary school teacher and every Friday she does a fingerpainting project with her class. Given the number of different colors needed, the amount of each color, and the amount of gray, your job is to calculate the number of kits needed for her class.

输入:

The input consists of one or more test cases, followed by a line containing only zero that signals the end of the input. Each test case consists of a single line of five or more integers, which are separated by a space. The first integer N is the number of different colors (3 ≤ N ≤ 12). Following that are N different nonnegative integers, each at most 1,000, that specify the amount of each color needed. Last is a nonnegative integer G ≤ 1,000 that specifies the amount of gray needed. All quantities are in ml.

输出:

The input consists of one or more test cases, followed by a line containing only zero that signals the end of the input. Each test case consists of a single line of five or more integers, which are separated by a space. The first integer N is the number of different colors (3 ≤ N ≤ 12). Following that are N different nonnegative integers, each at most 1,000, that specify the amount of each color needed. Last is a nonnegative integer G ≤ 1,000 that specifies the amount of gray needed. All quantities are in ml.

样例输入:

3 40 95 21 0
7 25 60 400 250 0 60 0 500
4 90 95 75 95 10
4 90 95 75 95 11
5 0 0 0 0 0 333
0

样例输出:

2
8
2
3
4

Hdu 2730 http://acm.hdu.edu.cn/showproblem.php?pid=2730

题目大意: 有n种颜色(不包括灰色),任意三种颜色各xml混合可以得到xml灰色,一整套颜料包括n种颜色,每种50ml,现给出对每种颜色以及灰色的需求量,要求至少需要多少套颜料才能达到要求。

解题思路: 可以从从1枚举答案,也可以二分答案,然后就是此题关键:知道n种颜色每一种的数量,要求可以最多得到多少灰色。次问题又可以转化为上面一题n同样与上面意义相同,上面的m即使这里的3


  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。