1689 建造高塔時(shí)間限制: 1 s空間限制: 128000 KB題目等級(jí) : **鉆石 Diamond** 題目描述 Description n有n種石塊，石塊能無(wú)限供應(yīng)。每種石塊都是長(zhǎng)方體，其中第i種石塊的長(zhǎng)、寬、高分別為li、wi、hi。石塊可以旋轉(zhuǎn)，使得其中兩維成為長(zhǎng)度和寬度，第三維成為高度。如果要把一個(gè)石塊放在另一個(gè)石塊上面，必須保證上面石塊的長(zhǎng)和寬都分別嚴(yán)格小于下面石塊的長(zhǎng)和寬。這意味著，即使兩塊長(zhǎng)寬相同的石塊也不能堆砌起來(lái)。 現(xiàn)在神犇想知道，最多能用上多少塊石頭呢？ 輸入描述 Input Description 第一行，N； 以下N行，每行三個(gè)數(shù)，表示第i種石頭的長(zhǎng)寬高。 輸出描述 Output Description 一個(gè)整數(shù)，表示最多能用上多少塊石頭。 樣例輸入 Sample Input 3 1 1 1 2 2 2 3 3 4 樣例輸出 Sample Output 3 數(shù)據(jù)范圍及提示 Data Size & Hint N≤50000，其余數(shù)字≤maxlongint。 分類標(biāo)簽 Tags **動(dòng)態(tài)規(guī)劃** /* n^2 60. */ #include<iostream> #include<cstdio> #include<algorithm> #define MAXN 50001 using namespace std; int n,tot,ans; struct data{int x,y,tot; }s[MAXN*6]; int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*f; } bool cmp(const data & x,const data & y) {if(x.x!=y.x) return x.x<y.x;return x.y<y.y; } int main() {int x,y,z;n=read();for(int i=1;i<=n;i++){x=read();y=read();z=read();s[++tot].x=x;s[tot].y=y;s[++tot].x=y;s[tot].y=x;s[++tot].x=y;s[tot].y=z;s[++tot].x=x;s[tot].y=z;s[++tot].x=z;s[tot].y=x;s[++tot].x=z;s[tot].y=y;}sort(s+1,s+tot+1,cmp);for(int i=1;i<=tot;i++){s[i].tot=1;for(int j=i-1;j>=1;j--){if(s[i].y>s[j].y&&s[i].x>s[j].x)s[i].tot=max(s[i].tot,s[j].tot+1);}}for(int i=1;i<=tot;i++)ans=max(ans,s[i].tot);printf("%d",ans);return 0; } /* nlogn. 左端點(diǎn)排序. 右端點(diǎn)從大到小排序. 防止左端點(diǎn)相等的點(diǎn)被更新. */ #include<iostream> #include<cstdio> #include<algorithm> #define MAXN 50001 using namespace std; int n,tot,ans,l=1,c[MAXN*6]; struct data{int x,y,tot; }s[MAXN*6]; int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*f; } int erfen(int x){int ll=0,r=l,mid;while(ll<r){mid=(r+ll)>>1;if(x>c[mid]) ll=mid+1;else r=mid;}return ll; } bool cmp(const data & x,const data & y) {if(x.x!=y.x) return x.x<y.x;return x.y>y.y; } int main() {int x,y,z;n=read();for(int i=1;i<=n;i++){x=read();y=read();z=read();s[++tot].x=x;s[tot].y=y;s[++tot].x=y;s[tot].y=x;s[++tot].x=y;s[tot].y=z;s[++tot].x=x;s[tot].y=z;s[++tot].x=z;s[tot].y=x;s[++tot].x=z;s[tot].y=y;}sort(s+1,s+tot+1,cmp);c[1]=s[1].y;for(int i=2;i<=tot;i++){s[i].tot=1;if(s[i].y>c[l]) c[++l]=s[i].y;else {int p=erfen(s[i].y);c[p]=s[i].y;}}printf("%d",l);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/nancheng58/p/6070769.html

總結(jié)

以上是生活随笔為你收集整理的Codevs 1689 建造高塔的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。