Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:非常经典的动态规划,用递归下的记忆化搜索来实现。我将整个实现流程和很多容易错的地方都注释起来,希望能够对那些比较困惑的朋友有所帮助。这程序花了我半个小时调试和写注释,题不在多,经典则行。好晚了,好累,睡觉~~

Posted by MathMars at 2011-11-11 00:48:24 on Problem 1088
In Reply To:非常经典的动态规划,用递归下的记忆化搜索来实现。我将整个实现流程和很多容易错的地方都注释起来,希望能够对那些比较困惑的朋友有所帮助。这程序花了我半个小时调试和写注释,题不在多,经典则行。好晚了,好累,睡觉~~ Posted by:gfedcba at 2009-02-28 03:37:51
其实吧,像这个矩阵完全是可以转化为一维线性表就行了,上下左右几个方向也很好表示的,(-c)(+1)(+c)(-1),然后也很容易判断是否在边界上。排序,转移很简单了。。。。ac,复杂度是O(r*c):指教指教呗,谢谢;
#include<stdio.h>

int r,c;
long f[10004],tt;
int p[10004],pos[10004],poss[10004],pp[5];


int maxx(int a,int b)
{
	if (a>b)
		return a;
	else
		return b;
}
void qsort(int a,int b)
{
	int i,j,tmp,k;
	i=a;j=b;
	k=p[(i+j)/2];
	while (i<=j)
	{
		while (p[i]<k) i++;
		while (p[j]>k) j--;
		if(i<=j)
		{
			tmp=p[i];p[i]=p[j];p[j]=tmp;

			tmp=pos[i];pos[i]=pos[j];pos[j]=tmp;
			poss[pos[i]]=i;poss[pos[j]]=j;
			
			i++;j--;
		}
	}
	if (a<j) qsort(a,j);
	if (i<b) qsort(i,b);
}
int main()
{
	int i,j;
	int max,tot;
	tot=0;
	scanf("%d%d",&r,&c);
	for (i=1;i<=r;i++)
		for (j=1;j<=c;j++)
		{
			scanf("%d",&tt);
			tot++;
			p[tot]=tt;
			pos[tot]=tot;
			poss[tot]=tot;
		}
	qsort(1,tot);
	max=0;
	for (i=1;i<=tot;i++)
	{	
		f[i]=1;
		pp[1]=pos[i]-c;pp[2]=pos[i]+1;pp[3]=pos[i]-1;pp[4]=pos[i]+c;
		for (j=1;j<=4;j++)
		{
			if ((pp[j]<=tot)&&(pp[j]>=1)&&(p[poss[pp[j]]]<p[i]))
			{
				if ((j==2)&&(pp[j]%c==1)) continue;
				if ((j==3)&&(pp[j]%c==0)) continue;
				f[i]=maxx(f[i],f[poss[pp[j]]]+1);
			}
		}
		max=maxx(max,f[i]);
	}
	printf("%d\n",max);
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator