首页 > 代码库 > uva--103Stacking Boxes +dp
uva--103Stacking Boxes +dp
题意:
其实就是把矩形嵌套扩大到了n维,但是规定这个n维的几何体是可以任意扭曲的。
思路:
就是按照矩形嵌套问题的思路,不过判定是否可以嵌套的时候,我们直接都排一下序就判断了(因为是可以任意扭曲的)。还有就是需要打印出整个序列,这里可以借用小白书上的思路,递归进行打印。
代码如下:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int st[50][15]; int map[50][50],d[50],n,m; int dp(int i) { if(d[i]>0) return d[i]; d[i]=1; for(int j=0;j<n;j++) if(map[i][j]) { int t=dp(j)+1; if(d[i]<t) d[i]=t; } return d[i]; } void print(int i) { printf("%d ",i+1); for(int j=0;j<n;j++) if(d[j]==d[i]-1&&map[i][j]) { print(j); break; } } int check(int a[],int b[]) { for(int i=0;i<m;i++) if(a[i]>=b[i]) return 0; return 1; } void Init() { memset(d,0,sizeof(d)); memset(map,0,sizeof(map)); } int main() { int i,j; while(scanf("%d%d",&n,&m)!=EOF) { for(i=0;i<n;i++) for(j=0;j<m;j++) scanf("%d",&st[i][j]); Init(); for(i=0;i<n;i++) for(j=0;j<n;j++) { int c[50],d[50]; for(int k=0;k<m;k++) { c[k]=st[j][k]; d[k]=st[i][k]; } sort(c,c+m); sort(d,d+m); if(check(d,c)) map[i][j]=1; } int ans=0,k; for(i=0;i<n;i++) { int t=dp(i); if(t>ans) { ans=t; k=i; } } printf("%d\n",ans); print(k); printf("\n"); } return 0; }
uva--103Stacking Boxes +dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。