继续练习记忆化搜索
求最大的矩形嵌套 在输出
记忆化搜索 和滑雪那题差不多
#include#include #include using namespace std; int dp[40]; int map[40]; bool vis[40]; int a[40][12]; int n,m; void print(int pos) { if(pos != map[pos]) print(map[pos]); printf("%d ",pos); } bool ok(int i,int j) { for(int k = 0; k < m; k++) { if(a[i][k] >= a[j][k]) return false; } return true; } int dfs(int u) { int max = 0; if(vis[u]) return dp[u]; for(int i = 1;i <= n; i++) { if(i == u) continue; if(!ok(u,i)) continue; int temp = dfs(i); if(max < temp) { max = temp; map[u] = i; } } vis[u] = true; dp[u] = max + 1; return dp[u]; } int main() { int i,j; while(scanf("%d %d",&n,&m)!=EOF) { for(i = 1; i <= n; i++) { for(j = 0; j < m; j++) { scanf("%d",&a[i][j]); } sort(a[i],a[i]+m); } int max = 0; int pos = 0; memset(vis,false,sizeof(vis)); memset(dp,0,sizeof(dp)); memset(map,0,sizeof(map)); for(i = 1;i <= n; i++) { int temp = dfs(i); if(max < temp) { max = temp; pos = i; } } printf("%d\n",max); int flag = 0; while(max--) { if(flag++) printf(" "); printf("%d",pos); pos = map[pos]; } puts(""); } return 0; }