8月6号的题目：HDU 1003&& POJ 1050&&HDU 1800&&HDU 2036&& POJ 1088（记忆化搜索）
Max Sum HDU 1003
一个求最大连续子序列：（有模板吧）
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 using namespace std; 5 int main() 6 { 7 int n,m,a[100005],i,j,k,l,r,s,MAX; 8 scanf("%d",&n); 9 for(i=1;i<=n;i++) 10 { 11 scanf("%d",&m); 12 for(j=1;j<=m;j++) 13 scanf("%d",&a[j]); 14 MAX=-1005; 15 for(j=1;j<=m;j++) 16 { 17 s=0; 18 for(k=j;k<=m;k++) 19 { 20 s+=a[k]; 21 if(s>MAX) 22 { 23 l=j; 24 r=k; 25 MAX=s; 26 } 27 if(s<0) 28 break; 29 } 30 } 31 printf("Case %d: ",i); 32 printf("%d %d %d ",MAX,l,r); 33 if(i!=n) 34 printf(" "); 35 } 36 return 0; 37 }//这个是常规思想（符合人脑的思维）
再来是模板：
1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 int main() 5 { 6 int T,a,k=0; 7 scanf("%d",&T); 8 while(T--) 9 { 10 k++; 11 int n,st=0,max=-999999999,i,j,sum=0,end=0; 12 scanf("%d",&n); 13 for(i=j=1;j<=n;j++) 14 { 15 scanf("%d",&a); 16 sum+=a; 17 if(sum>max) //更新最大值 18 { 19 max=sum; 20 st=i; //更新起点 21 end=j; //更新终点 22 } 23 if(sum<0) //sum<0，抛弃前面的点 24 { 25 i=j+1; //更新起点 26 sum=0; //和清0 27 } 28 }//只有一个循环语句 29 printf("Case %d: %d %d %d ",k,max,st,end); 30 if(T) 31 printf(" "); 32 } 33 return 0; 34 }
To the Max POJ 1050
就是上面题目的二维形式吧。
摘自：http://blog.163.com/xiangzaihui@126/blog/static/166955749201161205044188/
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<string.h> 5 using namespace std; 6 int a[105][105],c[105][105]; 7 int main() 8 { 9 int n,i,j,k,sum,max1,MAX; 10 while(scanf("%d",&n)!=EOF) 11 { 12 memset(c,0,sizeof(c)); 13 MAX=0; 14 for(i=1;i<=n;i++) 15 for(j=1;j<=n;j++) 16 scanf("%d",&a[i][j]); 17 for(i=1;i<=n;i++) 18 { 19 for(j=i;j<=n;j++) 20 { 21 sum=0;max1=0; 22 for(k=1;k<=n;k++) 23 { 24 c[k][j]=c[k][j-1]+a[j][k]; 25 sum+=c[k][j]-c[k][i-1]; 26 if(sum<0) 27 sum=0; 28 if(sum>max1) 29 max1=sum; 30 } 31 if(max1>MAX) 32 MAX=max1; 33 } 34 } 35 printf("%d ",MAX); 36 37 } 38 return 0; 39 }
这个题目原本以为用搜索的来做的。但是发现有四个点要考虑！！会超时的吧。
后来看到网上的DP就是压缩时间！（应该是四维变三维的）
上面的代码是这个意思：
压缩竖坐标（把竖坐标用上题的方法求），i和j表示横坐标。那个c[k][j]记录的是第k竖的j横的：a[1][k],a[2][k],a[3][k],...a[j][k].
那么的话：sum把横坐标i到j的一系列数相加，当sum小于零就从新开始。
Flying to the Mars HDU 1800
一道简单的求最长不上升子序列长度的问题（先排序）：
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<string.h> 5 using namespace std; 6 int main() 7 { 8 int a[3005],n,i,MAX,c[3005],len,left,right,mid; 9 while(scanf("%d",&n)!=EOF) 10 { 11 for(i=1;i<=n;i++) 12 scanf("%d",&a[i]); 13 sort(a+1,a+n+1); 14 len=0;memset(c,0,sizeof(c)); 15 c[0]=1000000005; 16 for(i=1;i<=n;i++) 17 { 18 if(c[len]>=a[i]) 19 { 20 len++; 21 c[len]=a[i]; 22 } 23 else 24 { 25 left=0; 26 right=len; 27 while(right-left>1) 28 { 29 mid=(left+right)/2; 30 if(c[mid]>=a[i]) 31 left=mid; 32 else 33 right=mid; 34 } 35 c[right]=a[i]; 36 } 37 } 38 printf("%d ",len); 39 } 40 return 0; 41 }
改革春风吹满地 HDU 2036
一道数学题：知道公式就知道做：
公式：
利用多边形（n边形）面积计算公式：S=0.5 * ( (x0*y1-x1*y0) + (x1*y2-x2*y1) + ... + (xn*y0-x0*yn) )，
其中点(x0，y0), (x1， y1), ... , (xn,，yn)为多边形上按逆时针顺序的顶点。
1 #include<iostream> 2 #include<algorithm> 3 #include<stdio.h> 4 using namespace std; 5 int main() 6 { 7 int n,i,x,y,x1,y1,x2,y2; 8 double sum; 9 while(scanf("%d",&n)!=EOF) 10 { 11 if(n==0) 12 break; 13 scanf("%d%d",&x,&y); 14 x1=x; 15 y1=y; 16 sum=0; 17 for(i=2;i<=n;i++) 18 { 19 scanf("%d%d",&x2,&y2); 20 sum+=x1*y2-x2*y1; 21 x1=x2; 22 y1=y2; 23 } 24 sum+=x1*y-x*y1; 25 printf("%.1lf ",sum/2); 26 } 27 return 0; 28 }
滑雪 POJ 1088
好像是最长下降子序列的二维形式：
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 using namespace std; 5 int b[4][2]={0,1,0,-1,1,0,-1,0}; 6 int n,m,a[105][105],dp[105][105]; 7 int dfs(int x,int y) 8 { 9 int x1,y1,i,max1; 10 if(dp[x][y]>1) 11 return dp[x][y]; 12 for(i=0;i<4;i++) 13 { 14 x1=x+b[i][0]; 15 y1=y+b[i][1]; 16 if(x1>=1&&x1<=n&&y1>=1&&y1<=m&&a[x1][y1]<a[x][y]) 17 { 18 max1=dfs(x1,y1); 19 if(max1+1>dp[x][y]) 20 dp[x][y]=max1+1; 21 } 22 } 23 return dp[x][y]; 24 } 25 int main() 26 { 27 int i,j,MAX; 28 while(scanf("%d%d",&n,&m)!=EOF) 29 { 30 for(i=1;i<=n;i++) 31 for(j=1;j<=m;j++) 32 { 33 scanf("%d",&a[i][j]); 34 dp[i][j]=1; 35 } 36 MAX=0; 37 for(i=1;i<=n;i++) 38 for(j=1;j<=m;j++) 39 { 40 dfs(i,j); 41 if(dp[i][j]>MAX) 42 MAX=dp[i][j]; 43 } 44 printf("%d ",MAX); 45 } 46 return 0; 47 }
这个代码与一维的有很多神似之处。。。。
什么是记忆化搜索呢？
搜索和动态规划各自的优缺点：
搜索的低效在于没有能够很好地处理重叠子问题；
动态规划虽然比较好地处理了重叠子问题，但是在有些拓扑关系比较复杂的题目面前，又显得无奈。
记忆化搜索正是在这样的情况下产生的，它采用搜索的形式和动态规划中递推的思想将这两种方法有机地综合在一起，扬长避短，简单实用，在信息学中有
着重要的作用。
用一个公式简单地说：记忆化搜索=搜索的形式+动态规划的思想。
我认为呢，关键点还是动态规划的思想！具体表现有一点（if ( Dp [i] != 0) return Dp[i] ;）
要是一开始没有头绪，就把他们分开来进行思考，之后再有机地结合。