2014
11-27

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