When Hawk comes to the foot of the mountain, the autochthons told him a great secret. There are many caves in the mountain. And each cave stores three diamonds: a red diamond (ruby), a blue diamond (sapphire), and a purple diamond (amethyst). The explorer can take only one diamond from each cave; otherwise the god will punish the greedy man.
Along the mountain, there are hundreds of caves. The caves are located in a straight line, and the explorer will go through the line, visiting the caves one after another. Hawk knows the values of the diamonds in each cave. Since he wants to make an exciting trip, he won't choose the same kind of diamonds in any two consecutive caves. That means, if Hawk choose a red diamond in this cave, then he won't choose the red one in the next cave.
Now, Hawk asks you to help him to determine how to pick the diamonds. He will tell you the values of diamonds in each cave. Please calculate the maximum value that Hawk can achieve.
The first line of the input contains an integer t (1 ≤ t ≤ 100), which denotes the number of cases. Then t cases followed. Each case begins with an integer n (1 ≤ n ≤ 10000), which denotes the number of caves. Then n lines followed, each line contains 3 integers, the number in the i-th line denote the values of the red diamond, the blue diamond, and the purple diamond in the i-th cave, respectively. The value of any diamond will be non-negative integer and less than 1000.
Problem Setter: cnHawk
Source: Tianjin Metropolitan Collegiate Programming Contest 2007Show Code - Run ID 634040 Submit Time: 2009-05-09 18:40:07 Language: GNU C++ Result: Accepted Pid: 2843 Time: 0.02 sec. Memory: 1356 K. Code Length: 0.7 K.-------------------------------------------------------------------------------- #include <iostream>#define MAX 10002using namespace std;int data[MAX][4];int GetMax(int a,int b) { if(a>b) return a; else return b; }int main() { int t,n,a,i,j; cin>>t; while(t--) { cin>>n; for(i=1;i<=n;i++) for(j=1;j<=3;j++) { scanf("%d",&data[i][j]); } int MM=-1,temp; for(i=n-1;i>=1;i--) { for(j=1;j<=3;j++) { if(j==1) temp=GetMax(data[i+1][2],data[i+1][3]); if(j==2) temp=GetMax(data[i+1][1],data[i+1][3]); if(j==3) temp=GetMax(data[i+1][1],data[i+1][2]); data[i][j]=data[i][j]+temp; if(data[i][j]>MM) MM=data[i][j]; } } printf("%d\n",MM); } return 0; }-------------------------------------------------------------------------------- Tianjin University Online Judge v1.2.4
转载于:https://www.cnblogs.com/forever4444/archive/2009/05/09/1453432.html
