UVA 103-Stacking Boxes
7377 단어 stack
코드는 다음과 같습니다.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXN 30+5
int a[MAXN][15],f[MAXN],m[MAXN][MAXN],r[MAXN],w[MAXN];
int k, n, ok;
int flag;
int cmp1(const void *_p,const void *_q)
{
int *p = (int *)_p;
int *q = (int *)_q;
return *p - *q;
}
int cmp2(const void *_p,const void *_q)
{
int *p = (int *)_p;
int *q = (int *)_q;
return a[*p][1] - a[*q][1];
}
void com(int i, int j)
{
for(int p = 1; p <= n; p ++)
if(a[r[i]][p] >= a[r[j]][p]) return;
ok = 1;
}
void dp(int i)
{
if(w[i] == -1) ;
else dp(w[i]);
if(w[i] == -1)
printf("%d",r[i]);
else printf(" %d",r[i]);
}
void solve()
{
memset(m,-1,sizeof(m));
memset(f,0,sizeof(f));
memset(w,-1,sizeof(w));
for(int i = 0; i < MAXN; i ++)
f[i] = 1;
for(int i = 1; i <= k; i ++)
{
int q = 0;
for(int j = i +1; j <= k; j ++)
{
ok = 0;
com(i,j);//printf("i=%d j=%d ok=%d
",i,j,ok);
if(ok&&f[j]<f[i]+1) {f[j] = f[i] + 1;w[j] = i;}
// printf("f[i]=%d f[j] = %d w[j] = %d
",f[i],f[j],w[j]);
}
}
int max = -1;
for(int i = 1; i <= k; i ++)
if(f[i] > max) {max = f[i];flag = i;}
printf("%d
",max);
//for(int i = 0; i <= k; i ++)
// printf("i = %d w[i] = %d
",i,w[i]);
dp(flag);
printf("
");
}
void input()
{
memset(a,0,sizeof(a));
while(scanf("%d%d",&k,&n) == 2)
{
for(int i = 1; i <= k; i ++)
for(int j = 1; j <= n; j ++)
scanf("%d",&a[i][j]);
for(int i = 1; i <= k; i ++)
qsort(a[i],n+1,sizeof(a[1][1]),cmp1);
for(int i = 0; i <= k; i ++)
r[i] = i;
qsort(r,k+1,sizeof(r[0]),cmp2);
solve();
}
}
int main()
{
input();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
초보자를 위한 SLL을 사용한 스택linkedlist를 사용하여 스택을 구현하는 코드를 작성해 보겠습니다. 전제 조건: linkedlist 작업에 대한 간략한 지식. 시작하기 전에 Stack이 무엇인지 알려주세요. 스택은 LIFO 원칙을 따르는 데이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.