hdu 1677（LIS+欲張り）
4618 ワード
1、http://acm.hdu.edu.cn/showproblem.php?pid=1677
2、タイトルの大意：今はたくさんの箱があります。長さと幅を知っています。小さいものは大きい中に入れることができますが、w 1を満足しなければいけません。最終的にはいくつの箱に統合することができますか？
一見欲張りな感じがしますが、数がちょっと大きいので、LISでやってもいいですが、LISでどうやって使えますか？
まず欲張りの考えに従って、所与のデータに並べ替えて、並べ替えの方法は先にwによって大きいから小さい順に並べ替えて、もしw等しいならば、hによって小さいから大きい順に並べ替えて、この方案は箱の幅が等しいことを解決するためで、中に入れられないので、例えば自分で模範例を書きました。
4 30 10 20 14 20/15/この例は、なぜ昇順が選択され、降順配列が選択されたのかを説明できます。
また、LISテンプレートの呼び出しに注意したいのですが、この問題は数字が同じで、自分でサンプルを書きました。
4 10 10 20 10 10 10 10 10 10 30/25/この例は、求める最長の上昇サブシーケンスが等しい場合を含むことを決定した。
最終的に出力される最長の上昇サブシーケンスの個数は、最終的に統合された箱の個数です。順序を整えて求められた最長の上昇サブシーケンスは、最終的に一番外側の箱に置くことです。間の箱は全部これらの箱に詰め込むことができます。
3、テーマ：
Nested Dolls
Time Limit：3000/1000 MS（Java/Others） メモリLimit：32768/32768 K（Java/Others）Total Submission（s）：1714 Acceepted Submission(s)：482
Problem Description
Dilwoth is the world’s most prominent collector of Russian ness ted dolls：he literally has thousands of them！You know，the wooden hollow dolls of different sizes of which the smalest doll is contained in the second smalest，and this doll is in turn contained in the next one and so forth.One day henders the the ferever is the the the wantinness Soness wintinness of wantinness wintinnes。After all、that would make his collection even more magnificent！ヘッドパッパッパックスeach ness ted doll and measres the width and heighhhhhhh 2 aach contained doll.A doll with width w 1 and heigh1 will fit in Anothehehehell of width w 2 andheighh2 fd andandand onlyiw w 1<2 andand afw 2 and thelelelelelelelelelelelelelelelelelelelelelelelelelelefs s s s s s s fw 1<2 awwwwwwwwwww1<2.aaaaaaaafs s s s s theafs s theaaafs s s s s s theafs the ve list of meass rements？
Input
On the first line of input is a single positive integer 1<=t==20 specifying the number of test cases to follw.Each test case begins apositive integer 1<=m==20000 on a line of sisisisisilf the the ininininininininstststststststststinininininininininininininininststststststststststststststststststststststststststinininininininininininininininininininininininininininininininininininininininininwhere wi is the width and hi the height of doll number i.1<=wi，hi==10000 for all i.
Output
For each test case there shound be one line of output containing the minimum number of nested dolls possible.
Sample Input
Sample Output
4、コード：
2、タイトルの大意：今はたくさんの箱があります。長さと幅を知っています。小さいものは大きい中に入れることができますが、w 1
一見欲張りな感じがしますが、数がちょっと大きいので、LISでやってもいいですが、LISでどうやって使えますか？
まず欲張りの考えに従って、所与のデータに並べ替えて、並べ替えの方法は先にwによって大きいから小さい順に並べ替えて、もしw等しいならば、hによって小さいから大きい順に並べ替えて、この方案は箱の幅が等しいことを解決するためで、中に入れられないので、例えば自分で模範例を書きました。
4 30 10 20 14 20/15/この例は、なぜ昇順が選択され、降順配列が選択されたのかを説明できます。
また、LISテンプレートの呼び出しに注意したいのですが、この問題は数字が同じで、自分でサンプルを書きました。
4 10 10 20 10 10 10 10 10 10 30/25/この例は、求める最長の上昇サブシーケンスが等しい場合を含むことを決定した。
最終的に出力される最長の上昇サブシーケンスの個数は、最終的に統合された箱の個数です。順序を整えて求められた最長の上昇サブシーケンスは、最終的に一番外側の箱に置くことです。間の箱は全部これらの箱に詰め込むことができます。
3、テーマ：
Nested Dolls
Time Limit：3000/1000 MS（Java/Others） メモリLimit：32768/32768 K（Java/Others）Total Submission（s）：1714 Acceepted Submission(s)：482
Problem Description
Dilwoth is the world’s most prominent collector of Russian ness ted dolls：he literally has thousands of them！You know，the wooden hollow dolls of different sizes of which the smalest doll is contained in the second smalest，and this doll is in turn contained in the next one and so forth.One day henders the the ferever is the the the wantinness Soness wintinness of wantinness wintinnes。After all、that would make his collection even more magnificent！ヘッドパッパッパックスeach ness ted doll and measres the width and heighhhhhhh 2 aach contained doll.A doll with width w 1 and heigh1 will fit in Anothehehehell of width w 2 andheighh2 fd andandand onlyiw w 1<2 andand afw 2 and thelelelelelelelelelelelelelelelelelelelelelelelelelelefs s s s s s s fw 1<2 awwwwwwwwwww1<2.aaaaaaaafs s s s s theafs s theaaafs s s s s s theafs the ve list of meass rements？
Input
On the first line of input is a single positive integer 1<=t==20 specifying the number of test cases to follw.Each test case begins apositive integer 1<=m==20000 on a line of sisisisisilf the the ininininininininstststststststststinininininininininininininininststststststststststststststststststststststststststinininininininininininininininininininininininininininininininininininininininininwhere wi is the width and hi the height of doll number i.1<=wi，hi==10000 for all i.
Output
For each test case there shound be one line of output containing the minimum number of nested dolls possible.
Sample Input
4
3
20 30 40 50 30 40
4
20 30 10 10 30 20 40 50
3
10 30 20 20 30 10
4
10 10 20 30 40 50 39 51
Sample Output
1
2
3
2
4、コード：
#include<stdio.h>
#include<string.h>
#define N 20005
#include<algorithm>
using namespace std;
int stack[N];
int dp[N];
int maxx;
int n;
struct node
{
int w;
int h;
}a[N];
int cmp(struct node b,struct node c)
{
if(b.w==c.w)
return b.h<c.h;
else return b.w>c.w;
}
void LIS()
{
//dp[i] i i ， ， i i +1
//int stack[N];
memset(dp,0,sizeof(dp));
memset(stack,0,sizeof(stack));
int top=0;
stack[top]=-99999999;
maxx=-1;
for(int i=1; i<=n; i++)
{
// a[i]> ，
if(a[i].h>=stack[top])
{
stack[++top]=a[i].h;
dp[i]=top;
}
// a[i] ， a[i]
else
{
int l=1,r=top;
while(l<=r)
{
int mid=(l+r)>>1;
if(a[i].h>=stack[mid])
{
l=mid+1;
}
else
r=mid-1;
}
// a[i]
stack[l]=a[i].h;
dp[i]=l;
}
if(dp[i]>maxx)
maxx=dp[i];
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].w,&a[i].h);
}
sort(a+1,a+n+1,cmp);
LIS();
printf("%d
",maxx);
}
return 0;
}
/*
10
4
30 10 20 13 20 14 20 15// ，
4
10 10 20 10 20 10 30 25//
4
10 15 20 10 20 30 30 25
3
20 30 40 50 30 40
4
20 30 10 10 30 20 40 50
3
10 30 20 20 30 10
4
10 10 20 30 40 50 39 51
*/