严华梁讲义.pptVIP

Poj4001 Catch the cow 思路：典型的有哪些信誉好的足球投注网站问题 伪代码如下： struct node { int data; int level; }; queuestruct node q; struct node root; root.x=n; root.level=0; q.push(root); while(!q.empty()) { struct node temp=q.front(); q.pop(); if(temp.x==k)couttemp.levelendl;break; q.push(struct node(x-1,level+1)); q.push(struct node(x+1,level+1)); q.push(struct node(2*x,level+1)); } 如何剪枝 之前走到过的x是不是可以不用往下有哪些信誉好的足球投注网站了？因为如果从当前的x可以找到解，那么之前就找到了。 更多的剪枝 if xk 2*x和x+1是不是都不需要有哪些信誉好的足球投注网站了 … 如何记录路径？ flag数组上想办法 poj1088 滑雪 思路：动态规划 L[i][j]=max(L[i-1][j]+1,L[i+1][j]+1,L[i][j-1]+1,L[i][j+1]+1) if h[i][j]h[i-1][j] … 初始： L[i][j]=1; i=1…R,j=1…C int maxlen=0; for(int i=1;i=R;i++) for(int j=1;j=C;j++) L[i][j]=max(L[i-1][j]+1,L[i+1][j]+1,L[i][j-1]+1,L[i][j+1]+1); if(L[i][j]maxlen) maxlen=L[i][j] 上面的代码存在什么问题？ L[i][j]=0, i=1…R,j=1…C int len(int i,int j) { if(L[i][j]!=0)return L[i][j]; int max=0; max=Max(len(i-1,j),len(i+1,j),len(i,j-1),len(i,j+1)) L[i][j]=max+1; return L[i][j]; } Poj2766 最大子矩阵 最大子段和(MSS) -1,5,3,5,-6 M[i]=M[i-1]+A[i] if M[i-1]+A[i]0 else M[i]=0 MSS=Max(M[i]),i=1…n sum=0; mss=0; for(i=1;i=n;i++) { if(sum0) sum=0; sum+=a[i]; if(summss) mss=sum; } 最大子矩阵 伪代码： A[n][n]原始矩阵 B[n]用来存放列的和 for(i=1;i=n;i++) { memset(B,0,sizeof(B)); for(j=i;j=n;j++) { for(int k=1;k=n;k++) B[k]+=A[j][k]; int tempMax= MSS(B); if(tempMaxMSSA) MSSA=tempMax; } } poj1833 排列 复杂度 O(1)O(lgn)O(n)O(nlogn)O(nN1) O(2n)O(n!)O(nn) 29！=8841761993739701954543616000000 1024！=5.41X102639 如何寻找下一个排列 123 132 213 a1…aiai+1…aj…an (aiai+1) a1…aj …ai…ai+1… (aj 为ai+1…an大于ai并且最小的元素） 1234 1243 1342 sort-1324 简单证明一下 a1…ai ai+1…aj…an ai’ a1…aj …ai…ai+1… a1…ai ai+1…aj…an ai’ a1…aj …ai…ai+1… a1…ai ai+1…aj…an ai’ a1…aj …ai…ai+1… 伪代码： void next(int A[],int n) { int i=n-1; while(i0A[i]A[i+1]) i--; if(i1)//如果完全逆序如321 sort(A);return; int min=65535; int minindex=i+1; int j=i+1; while(j=n) { //大于A[i]并且最小 if(A[j]A[i] A[j]min) { min=A[j]; mi