Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
System Crawler (2015-11-18)
Description
The game can be played by two or more than two players. It consists of a chessboard（棋盘）and some chessmen（棋子）, and all chessmen are marked by a positive integer or “start” or “end”. The player starts from start-point and must jumps into end-point finally. In the course of jumping, the player will visit the chessmen in the path, but everyone must jumps from one chessman to another absolutely bigger (you can assume start-point is a minimum and end-point is a maximum.). And all players cannot go backwards. One jumping can go from a chessman to next, also can go across many chessmen, and even you can straightly get to end-point from start-point. Of course you get zero point in this situation. A player is a winner if and only if he can get a bigger score according to his jumping solution. Note that your score comes from the sum of value on the chessmen in you jumping path.
Your task is to output the maximum value according to the given chessmen list.
Input
N value_1 value_2 …value_N
It is guarantied that N is not more than 1000 and all value_i are in the range of 32-int.
A test case starting with 0 terminates the input and this test case is not to be processed.
Output
Sample Input
Sample Output
10
3
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
int value[maxn];
int dp[maxn];
int main(){
int n;
//scanf("%d",&n);
while(scanf("%d",&n)!=EOF){
if(n==)
break;
for(int i=;i<=n;i++){
scanf("%d",&value[i]);
dp[i]=value[i];
}
int ans=-;
for(int i=;i<=n;i++){
for(int j=;j<i;j++){
if(value[i]>value[j]&&dp[i]<dp[j]+value[i])
dp[i]=dp[j]+value[i]; }
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
}
return ;
}
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
prayerhgq (2015-08-04)
System Crawler (2015-11-23)
Description
The researchers have n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions (xi, yi, zi). A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height.
They want to make sure that the tallest tower possible by stacking blocks can reach the roof. The problem is that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block because there has to be some space for the monkey to step on. This meant, for example, that blocks oriented to have equal-sized bases couldn't be stacked.
Your job is to write a program that determines the height of the tallest tower the monkey can build with a given set of blocks.
Input
representing the number of different blocks in the following data set. The maximum value for n is 30.
Each of the next n lines contains three integers representing the values xi, yi and zi.
Input is terminated by a value of zero (0) for n.
Output
Sample Input
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
struct node{
int x,y,z;
}dp[maxn];
bool cmp(const struct node t1,const struct node t2){
if(t1.x!=t2.x)
return t1.x<t2.x;
return t1.y<t2.y;
}
int main(){
int cas=;
int n;
while(scanf("%d",&n)!=EOF){
int cnt=;
if(n==)
break;
int tx,ty,tz;
for(int i=;i<=n;i++){
scanf("%d%d%d",&tx,&ty,&tz);
dp[cnt].x=tx,dp[cnt].y=ty,dp[cnt].z=tz,cnt++;
dp[cnt].x=tx,dp[cnt].y=tz,dp[cnt].z=ty,cnt++;
dp[cnt].x=ty,dp[cnt].y=tx,dp[cnt].z=tz,cnt++;
dp[cnt].x=ty,dp[cnt].y=tz,dp[cnt].z=tx,cnt++;
dp[cnt].x=tz,dp[cnt].y=tx,dp[cnt].z=ty,cnt++;
dp[cnt].x=tz,dp[cnt].y=ty,dp[cnt].z=tx,cnt++;
}
sort(dp,dp+cnt,cmp); for(int i=;i<cnt;i++){
int tmp=-;
for(int j=;j<i;j++){
if((((dp[i].x>dp[j].x)&&(dp[i].y>dp[j].y))||((dp[i].x>dp[j].y)&&(dp[i].y>dp[j].x)))&&(dp[j].z>tmp)){
tmp=dp[j].z;
}
}
if(tmp!=-)
dp[i].z+=tmp;
}
int ans=-;
for(int i=;i<cnt;i++){
ans=max(ans,dp[i].z); } printf("Case %d: maximum height = %d\n",cas++,ans);
}
return ;
}