描述 看过电影《心慌方》吗？非常经典的一部电影，推荐上完机后同学们看一看，介绍在这里。 /subject/1305903/
现在我们开始建造心慌方： 我们的目的是让心慌方里最最里层的人要尽可能费多的力气才能逃出来，也就是说，我们需要把心慌方 嵌套得尽可能多的层数。 想象一个3维的空间，<1,2,3>分别代表这个立方体的长宽高。那么，一个<2,3,4>的立方体则可以把前一个立方体装下。现在的问题是，给K个N维体（二维的话我们可以想象为平面上，三维可以想象成空间里，7维的话...我也不知道想象成啥了），请问，我们能构造的最多层的心慌方有几层？ 注意，<d1,d2,d3...dn>和<e1,e2,e3...en>这样两个n维的方，只要存在某个序列<a1,a2,a3...an>使得<d(a1),d(a2),d(a3)...d(an)>里面每一项d(a1)<e1&&d(a2)<e2...d(an)<en的话，我们就认为第一个方是可以装在第二个方里。以三维举例，<3,1,2>是可以装在<2,4,3>里的，因为<3,1,2>可以旋转为<1,3,2>而且1<2&&3<4&&2<3，因此可以装入
输入
数据组数T<=100
以下T组每组以
K,N开头(1<=K<=30,1<=N<=10)
以下K行，每行有N个数字，代表一个心慌方
输出
输出最多层的心慌方层数
样例输入
1
5 2
3 7
8 10
5 2
9 11
21 18
样例输出
5
提示
combine dynamic programming and be greedy
#include <iostream>#include <algorithm>using namespace std;int n;bool cmp(int a[], int b[]){int i;for(i = 0; i < n; i ++)if(a[i] >= b[i])return false;return true;}int dp[100];int x[100][20], p[100][20];bool has[100];int main(){int t;int i, j, m, mm, jj;cin >> t;while(t --){int k;cin >> k >> n;bool flag;for(i = 0; i < k; i ++){for(j = 0; j < n; j ++)cin >> x[i][j];sort(x[i], x[i] + n);}for(i = 0; i < k; i ++)has[i] = false;for(i = 0; i < k; i ++){for(j = 0; j < k; j ++){flag = false;if(!has[j]){flag = true;for(jj = 0; jj < k; jj ++){if(!has[jj] && jj != j && cmp(x[jj], x[j])){flag = false;break;}}}if(flag){for(jj = 0; jj < n; jj ++)p[i][jj] = x[j][jj];has[j] = true;break;}}}for(i = 0; i < k; i ++)dp[i] = 1;for(i=k-2; i>=0; i--)for(j=i+1; j<k; j++){flag = true;for(jj = 0; jj < n; jj ++)if(p[j][jj] <= p[i][jj]){flag = false;break;}if(flag&&dp[i]<dp[j]+1)dp[i]=dp[j]+1;}int max=0;for(i=0; i<k; i++){if(dp[i]>max)max=dp[i];}cout << max << '\n';}return 0;}
如果觉得《1712 心慌方》对你有帮助，请点赞、收藏，并留下你的观点哦！
