//同样可以定义一个结构，但没有必要#include<iostream>#include<fstream>#include<cstdlib>using namespace std;ifstream fin("C:\\data13.in");struct rect{rect(int a=0,int b=0):length(a),width(b){}int length;int width;};rect arr[100];int RectGraph[100][100];int maxlength[100];int prev[100];int n;//排序影响下面的运算过程，可以不排序，对总时间影响不大。这里是为了测试方便。void sort(){for(int i=1;i<n;++i){for(int j=i;j>0;--j){rect rt;if(arr[j].length>arr[j-1].length){rt=arr[j];arr[j]=arr[j-1];arr[j-1]=rt;}else if(arr[j].length==arr[j-1].length&&arr[j].width>arr[j-1].width){rt=arr[j];arr[j]=arr[j-1];arr[j-1]=rt;}elsebreak;}}}void Init(){int length,width;int temp;n=0;while(fin>>length>>width){if(length<width){temp=length;length=width;width=temp;}rect rt(length,width);arr[n++]=rt;}sort();for(int i=0;i<n;++i)maxlength[i]=1;memset(RectGraph,0,sizeof(RectGraph));for(int i=1;i<n;++i){for(int j=i-1;j>=0;--j){if(arr[j].width>=arr[i].width)RectGraph[i][j]=1;}}}void DP(){maxlength[0]=1;prev[0]=0;for(int i=1;i<n;++i){int max=1;int prec=i;for(int j=0;j<i;++j){if(RectGraph[i][j]==1){if(max<maxlength[j]+1){max=maxlength[j]+1;prec=j;}}}maxlength[i]=max;prev[i]=prec;}}void print(){int max=0;int pos=0;for(int i=0;i<n;++i){if(maxlength[i]>max){max=maxlength[i];pos=i;}}while(maxlength[pos]!=1){cout<<"Rect("<<arr[pos].length<<","<<arr[pos].width<<")\t";pos=prev[pos];}cout<<"Rect("<<arr[pos].length<<","<<arr[pos].width<<")"<<endl;}int main(){Init();DP();print();system("pause");return 0;}
如果觉得《(GAD)NestedRectangle》对你有帮助，请点赞、收藏，并留下你的观点哦！
