Posted on 2009-08-27 16:30
Uriel 阅读(426)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
DP
这题自己先结构体二级排序再按一重的做WA得郁闷，以为方法错了。。然后用了网上搜的一个方法，dp数组的下标直接是第几个数，后来发现自己sort有个小错，自己的方法也过了
网上的方法：
/**//*Problem: 1609 User: Uriel
Memory: 236K Time: 16MS
Language: C++ Result: Accepted*/
#include<stdio.h>
#include<string.h>
int dp[120][120],i,j,a[120][120],t,l,r;
int max(int a,int b)
{
return a>=b?a:b;
}
int main()
{
while(1)
{
scanf("%d",&t);
if(t==0)break;
memset(a,0,sizeof(a));
for(i=1;i<=t;i++)
{
scanf("%d %d",&l,&r);
a[l][r]++;
}
for(i=1;i<=100;i++)
{
for(j=1;j<=100;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
dp[i][j]+=a[i][j];
}
}
printf("%d\n",dp[100][100]);
}
printf("*\n");
return 0;
}
/**//*Problem: 1609 User: Uriel
Memory: 176K Time: 32MS
Language: C++ Result: Accepted*/
#include<stdio.h>
#include<stdlib.h>
int i,j,max,t,dp[10010];
struct In{
int l;
int r;
}S[10010];
int cmp( const void *a , const void *b )
{
struct In *c = (In *)a;
struct In *d = (In *)b;
if(c->l != d->l) return d->l - c->l;
else return d->r - c->r;
}
int main()
{
while(1)
{
scanf("%d",&t);
if(t==0)break;
for(i=1;i<=t;i++)
{
scanf("%d %d",&S[i].l,&S[i].r);
}
qsort(&S[1],t,sizeof(S[1]),cmp);
dp[0]=0;
S[0].r=0;
max=0;
for(i=1;i<=t;i++)
{
dp[i]=1;
for(j=0;j<i;j++)
{
if(S[i].r<=S[j].r && dp[j]+1>dp[i])
{
dp[i]=dp[j]+1;
}
if(dp[i]>max)max=dp[i];
}
}
printf("%d\n",max);
}
printf("*\n");
return 0;
}