装饰网站建设的背景,seo就业前景,建设银行官方招聘网站,建设网站建设什么挣钱1689 建造高塔时间限制: 1 s空间限制: 128000 KB题目等级 : **钻石 Diamond**
题目描述 Description
n有n种石块#xff0c;石块能无限供应。每种石块都是长方体#xff0c;其中第i种石块的长、宽、高分别为li、wi、hi。石块可以旋转#xff0c;使得其中两维成为长度和宽度石块能无限供应。每种石块都是长方体其中第i种石块的长、宽、高分别为li、wi、hi。石块可以旋转使得其中两维成为长度和宽度第三维成为高度。如果要把一个石块放在另一个石块上面必须保证上面石块的长和宽都分别严格小于下面石块的长和宽。这意味着即使两块长宽相同的石块也不能堆砌起来。
现在神犇想知道最多能用上多少块石头呢
输入描述 Input Description
第一行N
以下N行每行三个数表示第i种石头的长宽高。
输出描述 Output Description
一个整数表示最多能用上多少块石头。
样例输入 Sample Input
3
1 1 1
2 2 2
3 3 4
样例输出 Sample Output
3
数据范围及提示 Data Size Hint
N≤50000其余数字≤maxlongint。
分类标签 Tags
**动态规划** /*
n^2 60.
*/
#includeiostream
#includecstdio
#includealgorithm
#define MAXN 50001
using namespace std;
int n,tot,ans;
struct data{int x,y,tot;
}s[MAXN*6];
int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9) xx*10ch-48,chgetchar();return x*f;
}
bool cmp(const data x,const data y)
{if(x.x!y.x) return x.xy.x;return x.yy.y;
}
int main()
{int x,y,z;nread();for(int i1;in;i){xread();yread();zread();s[tot].xx;s[tot].yy;s[tot].xy;s[tot].yx;s[tot].xy;s[tot].yz;s[tot].xx;s[tot].yz;s[tot].xz;s[tot].yx;s[tot].xz;s[tot].yy;}sort(s1,stot1,cmp);for(int i1;itot;i){s[i].tot1;for(int ji-1;j1;j--){if(s[i].ys[j].ys[i].xs[j].x)s[i].totmax(s[i].tot,s[j].tot1);}}for(int i1;itot;i)ansmax(ans,s[i].tot);printf(%d,ans);return 0;
} /*
nlogn.
左端点排序.
右端点从大到小排序.
防止左端点相等的点被更新.
*/
#includeiostream
#includecstdio
#includealgorithm
#define MAXN 50001
using namespace std;
int n,tot,ans,l1,c[MAXN*6];
struct data{int x,y,tot;
}s[MAXN*6];
int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9) xx*10ch-48,chgetchar();return x*f;
}
int erfen(int x){int ll0,rl,mid;while(llr){mid(rll)1;if(xc[mid]) llmid1;else rmid;}return ll;
}
bool cmp(const data x,const data y)
{if(x.x!y.x) return x.xy.x;return x.yy.y;
}
int main()
{int x,y,z;nread();for(int i1;in;i){xread();yread();zread();s[tot].xx;s[tot].yy;s[tot].xy;s[tot].yx;s[tot].xy;s[tot].yz;s[tot].xx;s[tot].yz;s[tot].xz;s[tot].yx;s[tot].xz;s[tot].yy;}sort(s1,stot1,cmp);c[1]s[1].y;for(int i2;itot;i){s[i].tot1;if(s[i].yc[l]) c[l]s[i].y;else {int perfen(s[i].y);c[p]s[i].y;}}printf(%d,l);return 0;
} 转载于:https://www.cnblogs.com/nancheng58/p/6070769.html
