化搜索。。用一个dp数组来记录套了几个。如果搜索过程中小于的直接不考虑
代码:
#include
#include
#include
using namespace std;
int n, m, i, j, Max, dp[35], way[35], save[35];
struct Box {
int d[15];
} b[35];
int judge(int small, int big) {
for (int i = 0; i < m; i ++)
if (b[small].d[i] >= b[big].d[i])
return 0;
return 1;
}
void dfs(int now, int num) {
for (int i = 1; i <= n; i ++) {
if (i != now && judge(now, i) && dp[i] < num + 1) {//dp[i] < num + 1 是记忆化搜索的关键。
dp[i] = num + 1;
save[num] = i;
dfs(i, num + 1);
}
}
if (Max < num) {
Max = num;
for (int j = 0; j < num; j ++)
way[j] = save[j];
}
}
int main() {
while (~scanf("%d%d", &n, &m)) {
Max = 0;
memset(dp, 0, sizeof(dp));
for (i = 1; i <= n; i ++) {
for (j = 0; j < m; j ++) {
scanf("%d", &b[i].d[j]);
}
sort(b[i].d, b[i].d + m);
}
dfs(0, 0);
printf("%d\n", Max);
for (i = 0; i < Max - 1; i ++)
printf("%d ", way[i]);
printf("%d\n", way[Max - 1]);
}
return 0;
}
|