首页 > ACM题库 > HDU-杭电 > HDU 3573-Buy Sticks[解题报告]HOJ
2014
11-27

HDU 3573-Buy Sticks[解题报告]HOJ

Buy Sticks

问题描述 :

Imyourgod need 3 kinds of sticks which have different sizes: 20cm, 28cm and 32cm. However the shop only sell 75-centimeter-long sticks. So he have to cut off the long stick. How many sticks he must buy at least.

输入:

The first line of input contains a number t, which means there are t cases of the test data.
There will be several test cases in the problem, each in one line. Each test cases are described by 3 non-negtive-integers separated by one space representing the number of sticks of 20cm, 28cm and 32cm. All numbers are less than 10^6.

输出:

The first line of input contains a number t, which means there are t cases of the test data.
There will be several test cases in the problem, each in one line. Each test cases are described by 3 non-negtive-integers separated by one space representing the number of sticks of 20cm, 28cm and 32cm. All numbers are less than 10^6.

样例输入:

2
3 1 1
4 2 2

样例输出:

Case 1: 2
Case 2: 3

#include<iostream>
using namespace std;
int main()
{
	int k1,k,i,n,x,y,z;
	while(cin>>n)
	{
		for(i=1;i<=n;i++)
		{
			k=0;
			cin>>x>>y>>z;
			while(x>=2&&z>=1)
			{
				z-=1;
				x-=2;
				k++;
			}
			while(x>=2&&y>=1)
			{
				y-=1;
				x-=2;
				k++;
			}
			while(z>=2)
			{
				z-=2;
				k++;
			}
			k1=x/3;
			x=x%3;
			k+=k1;
			while(z>=1&&y>=1)
			{
				z-=1;
				y-=1;
				k++;
			}
			while(y>=2)
			{
				y-=2;
				k++;
			}
			while(x>=2)
			{
				x-=2;
				k++;
			}
			if(x!=0||y!=0||z!=0)
				k++;
			cout<<"Case "<<i<<": "<<k<<endl;
		}
	}
}

  1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c