1609.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 41 行

#include "stdio.h"
#include "memory.h"
#define max(a,b) (((a)>(b))?(a):(b))

short ans[101][101];
short num[101][101];

int main()
{
	short n, i, j, k;
	
	while(1)
	{
		scanf( "%hd", &n );
		if( n == 0 ) break;

		memset( num, 0, sizeof(num) );
		memset( ans, 0, sizeof(ans) );

		for( k=0; k<n; k++ )
		{
			scanf( "%hd %hd", &i, &j );
			num[i][j]++;
		}

		for( i=1; i<=100; i++ )
		for( j=1; j<=100; j++ )
		{
			ans[i][j] = num[i][j] + max( ans[i-1][j],ans[i][j-1] );
		}

		printf( "%hd\n", ans[100][100] );
	}
	printf( "*\n" );

	return 0;
}