Home > Old Blog Posts > poj 1609

poj 1609


第一道完全在Linux下编写编译AC的题
乍一看很容易设计出一个O(n^2)的DP,但是会超时,
注意到l和m的范围都很小,可以想像,
若以l为横轴,m为纵轴,所有点都在100*100的范围内。
想到了什么?数字三角形!
设F(i,j)表示走到点(i,j)时的最大值,则
F(i,j)=Max(F(i-1,j),F(i,j-1))+num[i,j]

#include<stdio.h>
#include<string.h>
int f[101][101],num[101][101],vis[101][101],n;
inline int max(int a, int b){
	return a>b?a:b;
}
void dp(int x, int y){
	vis[x][y]=1;
	f[x][y]=num[x][y];
	if(x-1>=1){
		if(!vis[x-1][y]) dp(x-1,y);
		f[x][y]=max(f[x][y],f[x-1][y]+num[x][y]);
	}
	if(y-1>=1){
		if(!vis[x][y-1]) dp(x,y-1);
		f[x][y]=max(f[x][y],f[x][y-1]+num[x][y]);
	}
}
int main(){
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	while(scanf("%d",&n)!=EOF){
		if(!n) break;
		int x,y;
		memset(f,0,sizeof(f));
		memset(num,0,sizeof(num));
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;++i){
			scanf("%d %d",&x,&y);
			++num[x][y];
		}
		dp(100,100);
		printf("%d\n",f[100][100]);
	}
	printf("*\n");
	return 0;
}
Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: