UVA 103

/*
这题说的的是 N 维的坐标, 每个盒子的N维坐标 可以进行 随意方式的调换
然后求出 A全部的坐标小于B的 则 A 可以嵌套在B中 然后 计算出最多的 盒子嵌套个数
简单的状态转移 我为何如此的弱
*/
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
const int maxn=35;
const int maxm=15;
int N[maxn][maxm];
int dp[maxn];
int lis,mlis,n,m,per[maxn];
bool mark[maxn][maxn];
stack<int>TT;
bool jud(int a,int b){
int f=0;
for(int i=0;i<m;i++)
if(N[a][i]<=N[b][i])
{ f=1; break; }
if(f) return false;
return true;
}
int main()
{ while(scanf("%d%d",&n,&m)==2){
per[0]=lis=0;
dp[0]=1;
for(int i=1;i<=n;i++) {
dp[i]=1; per[i]=0;
}
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++)
scanf("%d",&N[i][j]);
sort(N[i],N[i]+m);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
mark[i][j]=jud(i,j);
for(int k=0;k<n;k++)
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
if(i!=j&&mark[i][j]&&dp[i]<dp[j]+1){
dp[i]=dp[j]+1;
per[i]=j;
}
if(dp[i]>lis){
lis=dp[i];
mlis=i;
}
}
printf("%d\n",lis);
TT.push(mlis);
int jj;
while(1){ jj=per[mlis];if(jj==0) break;TT.push(jj);mlis=jj; }
jj=TT.top();TT.pop();
printf("%d",jj);
while(!TT.empty()){ jj=TT.top();TT.pop();printf(" %d",jj); }
printf("\n");
}
return 0;
}
上一篇:Python version 3.6 required, which was not found in the registry错误解决


下一篇:组合 Lucas定理