题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1609
方法一：转化为求一维最长上升子序列。O(nlogn)
#include<iostream>
#include<algorithm>
using namespace std;
int b[10005];
int n;
typedef struct node
{
int l,m;
bool operator<(node t)
{
if(l<t.l) return 1;
else if(l==t.l&&m<t.m) return 1;
else return 0;
}
}block;
block a[10005];
int LIS()
{
int L=0;
for(int i=1;i<=n;i++)
{
int ll=1,rr=L;
while(ll<=rr)
{
int mid=(ll+rr)/2;
if(b[mid]<=a[i].m) ll=mid+1;
else rr=mid-1;
}
b[ll]=a[i].m;
if(ll>L) L++;
}
return L;
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].l,&a[i].m);
sort(a+1,a+n+1);
printf("%d\n",LIS());
}
printf("*\n");
return 0;
}
方法二：状态转移方程为：f[i][j]=max{f[i-1][j],f[i][j-1]}+a[i][j].
#include<iostream>
using namespace std;
#define max(x,y) (x>y?x:y)
int a[105][105],f[105][105];
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n)
{
int i,j,k,s;
memset(a,0,sizeof(a));
memset(f,-1,sizeof(f));
f[0][0]=0;
f[0][1]=0;
f[1][0]=0;
int xx=0,yy=0;
for(i=1;i<=n;i++)
{
scanf("%d%d",&k,&s);
if(xx<k) xx=k;
if(yy<s) yy=s;
a[k][s]++;
}
for(i=1;i<=xx;i++)
for(j=1;j<=yy;j++)
{
if(f[i-1][j]!=-1)
f[i][j]=max(f[i][j],f[i-1][j]+a[i][j]);
if(f[i][j-1]!=-1)
f[i][j]=max(f[i][j],f[i][j-1]+a[i][j]);
}
int ans=0;
for(i=1;i<=xx;i++)
for(j=1;j<=yy;j++)
if(ans<f[i][j]) ans=f[i][j];
printf("%d\n",ans);
}
printf("*\n");
return 0;
}
posted on 2010-09-07 21:08
wuxu 阅读(640)
评论(0) 编辑 收藏 引用 所属分类:
动态规划