题意：给出一串数字，求出其中某段连续的数字之和最大的值，同时要输出起点的位置和终点的位置~~~
方法一：
用sum记录某一段和的值，maxx为目前为止最大的sum值，当sum+a[i]<0时，sum清零，同时更新起点值~，当sum>max时，使max=sum，同时更新要输出的起点值start以及要输出的终点值end~
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; int main()
{
int t,n,cas=;
scanf("%d",&t);
while(t--)
{
cas++;
int i,j,sum=,start=,endd=,a,maxx=-,f,e;
scanf("%d",&n);
for(i=,f=,e=;i<n;i++)
{
scanf("%d",&a);
sum+=a;
if(sum>maxx)
{
maxx=sum; //跟新要输出的最大值，起点值，终点值~
start=f;
endd=i;
}
if(sum<)
{
sum=; //清零~并更新下一组数字的起点值~
f=i+;
}
e=i;
}
printf("Case %d:\n",cas);
printf("%d %d %d\n",maxx,start+,endd+);
if(t) printf("\n");
}
return ;
}
//memory：228KB time：0ms
POJ 1050 To the Max
题意：
给出一个矩阵，求出其中最大的子矩阵之和~其实与上题很相似~
#include<iostream>
#include<cstring>
using namespace std;
#define N 110
int a[N][N];
int b[N];
int main(){
int n,r;
cin>>r;
memset(a,,sizeof(a));
for(int i=;i<=r;++i)
for(int j=;j<=r;++j)
{
cin>>a[i][j];
a[i][j]+=a[i-][j];
}
int max=a[][];
for(int i=;i<=r-;++i)
for(int j=i+;j<=r;++j)
{
memset(b,,sizeof(b));
for(int k=;k<=r;++k)
{
if(b[k-]>=)
b[k]=b[k-]+a[j][k]-a[i][k];
else
b[k]=a[j][k]-a[i][k];
if(max<b[k])
max=b[k];
}
}
cout<<max<<endl;
}
//memory：276KB time：32ms
HDU 1800 Flying to the Mars
其实就是求排列（从大到小）好的最长上升子序列长度~
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; class A
{
public:
int x,id;
}a[]; bool comp(A k,A y)
{
return k.x>y.x;
} int main()
{
int n;
while(~scanf("%d",&n))
{
int i,j,number=,minn;
memset(a,,sizeof(a));
for(i=;i<n;i++)
scanf("%d",&a[i].x);
sort(a,a+n,comp);
for(i=;i<n;i++)
if(a[i].id==)
{
number++;
a[i].id=;
minn=a[i].x;
for(j=i+;j<n;j++)
if(a[j].id== && a[j].x<minn)
{
minn=a[j].x;
a[j].id=;
}
}
printf("%d\n",number);
}
}
//memory：252KB time：312ms
HDU 2036 改革春风吹满地
题意：求面积~
该题目是有公式的~
代码：
#include <iostream>//这是直接用叉积求多边形面积的
#include <algorithm>
#include <cstdio>
#include <string.h>
#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;
int main()
{
double s;
int n,i;
int x1,y1,x2,y2,x3,y3;
while(scanf("%d",&n),n)
{ s=;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for(i=;i<n;i++)
{
scanf("%d%d",&x3,&y3);
s+=(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
x2=x3;y2=y3;
}
s=s>?s:-s;
printf("%.1lf\n",s*0.5); }
return ;
}
//memory：240KB time：0ms
POJ 1088 滑雪
题意：找出最长的路径~
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; int r,c,a[][],dp[][],add[][]={{-,},{,},{,-},{,}}; int get_high(int x,int y)
{
if(dp[x][y]>)
return dp[x][y];
int maxx=,i,j,hx,hy;
for(i=;i<;i++)
{
hx=x+add[i][];
hy=y+add[i][];
if(a[x][y]>a[hx][hy] && hx>= && hy>= && hx<r && hy<c)
{
int h=get_high(hx,hy)+;
if(h>maxx) maxx=h;
}
}
return maxx;
} int main()
{
int i,j,maxx;
while(~scanf("%d%d",&r,&c))
{
memset(dp,,sizeof(dp));
for(i=;i<r;i++)
for(j=;j<c;j++)
{
scanf("%d",&a[i][j]);
dp[i][j]=;
}
for(i=,maxx=;i<r;i++)
for(j=;j<c;j++)
{
dp[i][j]=get_high(i,j);
if(dp[i][j]>maxx)
maxx=dp[i][j];
}
printf("%d\n",maxx);
}
return ;
}
//memory：224KB time：16ms