首页 » 技术分享 » 春校赛--求索溪边的砖

春校赛--求索溪边的砖

　
评论关闭　800次浏览

春校赛–求索溪边的砖 (10分)

众所周知，求索溪边堆了很多砖。
这些砖的长宽高规格不太一样。 一共有n{n<=30}种砖，第i种砖的长宽高分别为{Xi,Yi,Zi}, {xi,yi,zi < 10000}，每种砖有无限多。学校开展桃花节需要将这些砖搬走, 高级搬砖工小胖接了活。

我们搬砖时都是将砖叠成一摞再搬。小胖的力气非常大，当然希望尽可能的摞到最高, 但是只有上面砖的底面两条边都小于下面砖底面相对的两条边时，才能叠稳，注意砖可以旋转。(如: 长宽高为[3,4,5]的砖能叠在[2，5，5]，[5,4,3]上,不能叠在[2,4,3]上)。 帮小胖算算他第一次最多能搬走多少砖。

输入描述

多组输入 ， 每组一个整数n{n<=30}表示砖的种类，接下来n行每行3个整数x,y,z {x,y,z < 10000}
n=0表示输入结束。

输出描述

n 行，每行一个整数表示该组样例中第一次最多能搬砖的数量

输入样例

  1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0

输出样例

2
3
7
6

明显的矩形嵌套，但我第一次写的时候不知道用dp啊，蠢死啊，加油啊！
上代码

#include"iostream" 
#include"stdio.h" 
#include"algorithm" 
#include"cstring" 
using namespace std;
 struct jx 
 { 
  int c,k; 
  }S[10001];
   bool cmp1(int a,int b) {  return a>b; } 
   int map[100][100],dp[100]; 
   int find(int x,int n) 
   {  
   if(dp[x])return dp[x];  
   for(int i = 0;i < n;i++)  
   if(map[x][i])  
   {      
   dp[x] = max(dp[x],find(i,n)+map[x][i]); 
    }  return dp[x];  
     }
int main()
{
int N,ans[1001],Q=0; 
while(~scanf("%d",&N))
{
    if(N==0)break;
    memset(dp,0,sizeof(dp));
    memset(map,0,sizeof(map));
 int p = 0;
 int q[3];
 p = 0;
 int a[5],L,j,ans1 = 0;
 for(int i = 0;i < N;i++)
 {
  
  scanf("%d%d%d",&a[0],&a[1],&a[2]);
     if(a[0]!=a[1]&&a[1]!=a[2]&&a[0]!=a[2])
        L = 3;
  else {
  if(a[0]==a[1]&&a[1]==a[2])L = 1;    
        else
        L = 2;  
    }
    sort(a,a+3,cmp1);
    if(L==3){
    S[p].c=a[1],S[p].k=a[2],p++;
    S[p].c=a[0],S[p].k=a[2],p++;
    S[p].c=a[0],S[p].k=a[1],p++;
       }
       else
       {
        S[p].c=a[0],S[p].k=a[1],p++;
  if(L==2)S[p].c=a[1],S[p].k = a[2],p++;
    }
    }
  for(int i = 0;i < p;i++)
  for(int j = 0;j < p;j++)
  if(i!=j)
  {
   if(S[i].c<S[j].c&&S[i].k<S[j].k)
   map[i][j] = 1;
  }
   for(int i = 0;i < p;i++)
   if(!dp[i])
   find(i,p);
   int Max = 0;
   for(int i = 0;i < p;i++)
   {
   Max = max(Max,dp[i]);
   }
   cout << Max + 1<<endl;}
 return 0;
 }

转载自原文链接, 如需删除请联系管理员。

原文链接：春校赛--求索溪边的砖，转载请注明来源！

赞 0