首页 > 代码库 > uva103-Stacking_Boxes
uva103-Stacking_Boxes
题目链接请戳 这里
解题思路
DAG上的动态规划。现对n个维度排序(感觉有维度的,先排序排序就行了
代码
#include<stdio.h> #include<string.h> #include<algorithm> #define N 40 using namespace std; bool G[N][N]; int box[N][N], dp[N]; int k, n; bool first; bool judge(int x, int y) { bool flag = true; for (int i = 0; i < n; i++) if (box[x][i] >= box[y][i]) flag = false; return flag; } int cal(int i) { int &ans = dp[i]; if (ans > 0) return ans; ans = 1; for (int j = 1; j <= k; j++) if (G[i][j]) ans = max(ans, cal(j) + 1); return ans; } void print_ans(int i) { if (first) { printf("%d", i); first = false; } else printf("% d", i); for (int j = 1; j <= k; j++) if (G[i][j] && dp[i] == dp[j] + 1) { print_ans(j); break; } } int main() { while (scanf("%d%d", &k, &n) != EOF) { memset(G, false, sizeof(G)); for (int i = 1; i <= k; i++) for (int j = 0; j < n; j++) scanf("%d", &box[i][j]); for (int i = 1; i <= k; i++) sort(box[i], box[i] + n); for (int i = 1; i <= k; i++) for (int j = 1; j <= k; j++) if (judge(i, j)) G[i][j] = true; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= k; i++) cal(i); int max_index = 1; for (int i = 1; i <= k; i++) if (dp[i] > dp[max_index]) max_index = i; first = true; printf("%d\n", dp[max_index]); print_ans(max_index); printf("\n"); } return 0; }
uva103-Stacking_Boxes
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。