这几天一直专心刷题。。。刷的是DP题，题目基本和下面博客上介绍的差不多
http://hi.baidu.com/lewutian/item/ffd19c2e640e17c1ef10f131
然后。。。贴代码
/*
HOJ 1003 MaxSum
以前做过，和上一题也差不多，记录位置即可。DP
*/
#include <iostream>
using namespace std;
int main()
{
int cas,cas2,i,n,sum,max,a,b,num,begin;
cin>>cas;
cas2=cas;
while(cas--)
{
sum=a=b=0;
begin=1;
max=-1001;
cin>>n;
for(i=0;i<n;i++)
{
cin>>num;
sum+=num;
if(sum>max)
{
max=sum;
a=begin;
b=i+1;
}
if(sum<0)
{
sum=0;
begin=i+2;
}
}
cout<<"Case "<<cas2-cas<<":\n"<<max<<' '<<a<<' '<<b<<endl;
if(cas)
cout<<endl;
}
}
/*
HOJ 1024 Max Sum Plus Plus
*/
#include <iostream>
using namespace std;
const int N=1000101,INF=0x80000000;
int d[N],g[N],a[N];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int i,j,m,n,t;
while(~scanf("%d%d",&m,&n))
{
for(i=1;i<=n;i++)
{
scanf("%d",a+i);
d[i]=g[i]=INF;
}
for(i=1;i<=n;i++)
{
t=min(i,m);
for(j=1;j<=t;j++)
{
d[j]=max(g[j-1],d[j])+a[i];
g[j-1]=max(g[j-1],d[j-1]);
}
g[j-1]=max(g[j-1],d[j-1]);
}
printf("%d\n",g[m]);
}
}
/*
HOJ 1025 Constructing Roads In JGShining's Kingdom
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int s[500001],dp[500001],g[500001];
int main()
{
int i,j,m,n,t,max,cas=1;
while(~scanf("%d",&n))
{
max=0;
memset(g,0x7F,4*n+8);
for(i=1;i<=n;i++)
{
scanf("%d%d",&t,&m);
s[t]=m;
}
for(i=1;i<=n;i++)
{
j=lower_bound(g+1,g+n+1,s[i])-g;
g[j]=s[i];
if(max<j)
max=j;
}
printf("Case %d:\nMy king, at most %d road",cas++,max);
if(max-1)
printf("s");
printf(" can be built.\n\n");
}
}
/*
HOJ 1058 Humble Numbers
一开始一直在纠结这么大的数据范围，不会超时吗。。。。。。
建4个位置，存储即可。每个数字都要乘2,3,5,7的，比较下，相同的时候增大位置。
*/
#include <iostream>
using namespace std;
int s[6000];
int t[4];
int min(int a,int b,int c,int d)
{
int m=a<b?a:b;
int n=c<d?c:d;
m=m<n?m:n;
if(m==a)
t[0]++;
if(m==b)
t[1]++;
if(m==c)
t[2]++;
if(m==d)
t[3]++;
return m;
}
int main()
{
int i,n;
s[0]=1;
t[0]=t[1]=t[2]=t[3]=0;
for(i=1;i<5842;i++)
s[i]=min(2*s[t[0]],3*s[t[1]],5*s[t[2]],7*s[t[3]]);
while(~scanf("%d",&i)&&i)
{
n=i-1;
printf("The %d",i);
i%=100;
if(i!=11 && i%10==1)
printf("st");
else if(i!=12 && i%10==2)
printf("nd");
else if(i!=13 && i%10==3)
printf("rd");
else
printf("th");
printf(" humble number is %d.\n",s[n]);
}
}
/*
HOJ 1059
分财产。。。简单多重背包问题，初始化为0即可，最终检测d[V]==V
*/
#include <iostream>
using namespace std;
const int MAXUP=60001;
int UP,d[MAXUP];
inline int max(int a,int b)
{
return a>b?a:b;
}
void zpack(int cost,int weight)
{
for(int i=UP;i>=cost;i--)
d[i]=max(d[i],d[i-cost]+weight);
}
void cpack(int cost,int weight)
{
for(int i=cost;i<=UP;i++)
d[i]=max(d[i],d[i-cost]+weight);
}
void mpack(int cost,int weight,int amount)
{
if(weight*amount>+UP)
{
cpack(cost,weight);
return;
}
int k=1;
while(k<amount)
{
zpack(cost*k,weight*k);
amount-=k;
k+=k;
}
zpack(cost*amount,weight*amount);
}
int main()
{
int s[7],cas=1,flag,i;
while(1)
{
UP=0;
flag=1;
for(i=1;i<=6;i++)
{
scanf("%d",s+i);
UP+=s[i]*i;
}
if(!UP)
break;
if(UP&1)
flag=0;
else
{
UP/=2;
memset(d+1,0,UP*4);
for(i=1;i<=6;i++)
mpack(i,i,s[i]);
if(d[UP]!=UP)
flag=0;
}
printf("Collection #%d:\nCan",cas++);
if(!flag)
printf("'t");
printf(" be divided.\n\n");
}
}
/*
HOJ 1078 FatMouse and Cheese
DFS，保存中间子问题结果，就叫动态规划了
*/
#include <iostream>
using namespace std;
int dp[102][102],map[102][102];
int k,n;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int DFS(int x,int y)
{
int max=0,t;
if(dp[x][y])
return dp[x][y];
for(int i=1;i<=k;i++)
for(int j=0;j<4;j++)
{
int a=x+i*dir[j][0];
int b=y+i*dir[j][1];
if(a>0&&a<=n&&b>0&&b<=n&&map[x][y]<map[a][b])
{
if(max<(t=DFS(a,b)))
max=t;
}
}
return dp[x][y]=max+map[x][y];
}
int main()
{
int i,j;
while(~scanf("%d%d",&n,&k))
{
if(n==-1&&k==-1)
continue;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
dp[i][j]=0;
}
DFS(1,1);
printf("%d\n",dp[1][1]);
}
}
/*
HOJ 1080 Human Gene Functions
LCS升级版~用递归写的，感觉好写一点。。。
*/
#include <iostream>
using namespace std;
char a[101],b[101];
int d[101][101];
int la,lb;
int s[5][5]={
5,-1,-2,-1,-3,
-1,5,-3,-2,-4,
-2,-3,5,-2,-2,
-1,-2,-2,5,-1,
-3,-4,-2,-1
};
int getCode(char ch)
{
if(ch=='A')
return 0;
if(ch=='C')
return 1;
if(ch=='G')
return 2;
if(ch=='T')
return 3;
return 0;
}
int DFS(int x,int y)
{
if(x<0&&y<0)
return 0;
if(x<0&&y>=0)
return DFS(-1,y-1)+s[4][getCode(b[y])];
if(x>=0&&y<0)
return DFS(x-1,-1)+s[getCode(a[x])][4];
if(d[x][y])
return d[x][y];
if(a[x]==b[y])
d[x][y]=DFS(x-1,y-1)+5;
else
d[x][y]=max(DFS(x-1,y-1)+s[getCode(a[x])][getCode(b[y])],max(DFS(x,y-1)+s[4][getCode(b[y])],DFS(x-1,y)+s[getCode(a[x])][4]));
return d[x][y];
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
memset(d,0,sizeof(d));
scanf("%d",&la);
scanf("%s",a);
scanf("%d",&lb);
scanf("%s",b);
printf("%d\n",DFS(la-1,lb-1));
}
}
/*
HOJ 1081 To The Max
Max sum ^ 3
*/
#include <iostream>
using namespace std;
const int N=101;
int map[N][N],s[N];
int main()
{
int i,j,k,n,ans,t;
while(~scanf("%d",&n))
{
ans=0x80000000;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&map[i][j]);
for(i=1;i<=n;i++)
{
memset(s,0,4*n+4);
for(j=i;j<=n;j++)
{
t=0;
for(k=1;k<=n;k++)
{
s[k]+=map[j][k];
if(t<0)
t=s[k];
else
t+=s[k];
if(ans<t)
ans=t;
}
}
}
printf("%d\n",ans);
}
}
/*
HOJ 1114 Piggy-Bank
完全背包问题。初始化时全部赋值为最大值即可
*/
#include <iostream>
using namespace std;
const int MAXD=5000001;
int UP,dp[MAXD];
inline int min(int a,int b)
{
return a<b?a:b;
}
void zpack(int cost,int value)
{
for(int i=cost;i<=UP;i++)
dp[i]=min(dp[i-cost]+value,dp[i]);
}
int main()
{
int cas,i,j,m,n,x,y;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d%d",&i,&UP,&n);
UP-=i;
memset(dp,0x7f,(UP+2)*sizeof(int));
dp[0]=0;
for(i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
zpack(y,x);
}
if(dp[UP]>0x7F000000)
printf("This is impossible.\n");
else
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[UP]);
}
}
/*
HOJ 1158 Employment Planning
一道简单的DP，每月都会招人，所以都计算一下。。。。。。
每个月*招人的状态，转移是选最大
*/
#include <iostream>
using namespace std;
int d[13][100],num[13];
int main()
{
int i,j,k,m,n,maxMan,minMoney,s,h,f,t;
while(~scanf("%d",&n)&&n)
{
maxMan=0;
scanf("%d%d%d",&h,&s,&f);
for(i=1;i<=n;i++)
{
scanf("%d",num+i);
if(maxMan<num[i])
maxMan=num[i];
}
d[1][num[1]]=(s+h)*num[1];
for(i=num[1]+1;i<=maxMan;i++)
d[1][i]=d[1][i-1]+s+h;
for(i=2;i<=n;i++)
for(j=num[i];j<=maxMan;j++)
{
minMoney=0x7FFFFFFF;
for(k=num[i-1];k<=maxMan;k++)
{
if(j>k)
t=h*(j-k)+j*s+d[i-1][k];
else
t=f*(k-j)+j*s+d[i-1][k];
if(minMoney>t)
minMoney=t;
}
d[i][j]=minMoney;
}
minMoney=0x7FFFFFFF;
for(i=num[n];i<=maxMan;i++)
if(minMoney>d[n][i])
minMoney=d[n][i];
printf("%d\n",minMoney);
}
}
/*
HOJ 1159 Common Subsequence
最长相同子序列，以前做过，优化下，没用memset，发现速度快了很多。。。
*/
#include <iostream>
using namespace std;
int dp[2013][2013];
char a[2013],b[2013];
int main()
{
int i,j,lena,lenb;
while(~scanf("%s%s",a,b))
{
lena=strlen(a);
lenb=strlen(b);
for(i=0;i<lena;i++)
dp[0][i]=0;
for(i=0;i<lenb;i++)
dp[i][0]=0;
for(i=0;i<lena;i++)
for(j=0;j<lenb;j++)
dp[i+1][j+1]=a[i]==b[j]?dp[i][j]+1:(dp[i+1][j]>dp[i][j+1]?dp[i+1][j]:dp[i][j+1]);
printf("%d\n",dp[lena][lenb]);
}
}
//刘汝佳的空间O（m）算法
#include <iostream>
using namespace std;
inline int max(int a,int b)
{
return a>b?a:b;
}
int dp[2013];
char a[2013],b[2013];
int main()
{
int i,j,lena,lenb,x;
while(~scanf("%s%s",a+1,b+1))
{
x=0;
lena=strlen(a+1);
lenb=strlen(b+1);
memset(dp,0,sizeof(dp));
for(i=1;i<=lena;i++)
for(j=1;j<=lenb;j++)
{
if(a[i]==b[j])
dp[j]=dp[j-1]+1;
else
{
if(i==j)
dp[j]=x;
else
{
x=dp[j];
dp[j]=max(dp[j-1],dp[j]);
}
}
}
printf("%d\n",dp[lenb]);
}
}
/*
HOJ 1171 Big Event in HDU
01背包。改变数量（k）和金额（j）的循环顺序，边二分边减。时效46MS
*/
#include <iostream>
using namespace std;
int dp[250001];
int s[51];
int num[51];
int main()
{
int i,j,k,max,up,up2,n,t,tn;
while(~scanf("%d",&n))
{
if(n<0)
continue;
dp[up=max=0]=1;
for(i=0;i<n;i++)
{
scanf("%d%d",s+i,num+i);
up+=s[i]*num[i];
}
up2=up/2;
for(i=0;i<n;i++)
{
for(k=1;k<num[i];k*=2)
{
num[i]-=k;
for(j=max;j>=0;j--)
{
if(dp[j]&&(t=j+s[i]*k)<=up2)
{
dp[t]=1;
if(max<t)
max=t;
}
}
}
{
for(j=max;j>=0;j--)
{
if(dp[j]&&(t=j+s[i]*num[i])<=up2)
{
dp[t]=1;
if(max<t)
max=t;
}
}
}
}
printf("%d %d\n",up-max,max);
}
}
/*
HOJ 1224 Free DIY Tour
*/
#include <iostream>
using namespace std;
int d[150],map[150][150],a[150],line[150],n;
void print(int x)
{
if(line[x]==-1)
{
printf("%d",1);
return;
}
print(line[x]);
printf("->%d",x);
return;
}
int main()
{
int m,i,j,x,y,cas,k=1;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",a+i);
a[++n]=0;
scanf("%d",&m);
memset(d,0,sizeof(d));
memset(map,0,sizeof(map));
memset(line,-1,sizeof(line));
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
map[x][y]=1;
}
for(i=1;i<=n;i++)
for(j=1;j<i;j++)
{
if(map[j][i]&&d[i]<d[j]+a[i])
{
line[i]=j;
d[i]=d[j]+a[i];
}
}
printf("CASE %d#\n",k++);
printf("points : %d\n",d[n]);
printf("circuit : ");
print(line[n]);
printf("->1\n");
if(cas)
printf("\n");
}
}
/*
HOJ 1421 搬寝室
状态的理解。每对物品的只有两种状态，取，或不取。
状态转移：dp[i][j]=min(dp[i-2][j-1]+a[i],dp[i-1][j])
另外，memset真心拖时间。。。
*/
#include <iostream>
using namespace std;
const int Max=0x7FFFFFFF;
int a[2012];
int dp[2013][2014];
inline int min(int a,int b)
{
return a<b?a:b;
}
int cmp(const void *a,const void *b)
{
return *(int *)b-*(int *)a;
}
int main()
{
int i,j,m,n;
while(~scanf("%d%d",&n,&m))
{
for(i=0;i<=n;i++)
dp[i][0]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
dp[i][j]=Max;
for(i=1;i<=n;i++)
scanf("%d",a+i);
qsort(a+1,n,4,cmp);
for(i=n;i>1;i--)
a[i]=(a[i]-a[i-1])*(a[i]-a[i-1]);
for(i=2;i<=n;i++)
for(j=1;j*2<=i;j++)
dp[i][j]=min(dp[i-2][j-1]+a[i],dp[i-1][j]);
printf("%d\n",dp[n][m]);
}
}
/*
HOJ 1422 重温世界杯
同MaxSum，状态有很多，但是发现当前状态sum<0，直接丢掉。。。
*/
#include <iostream>
using namespace std;
int s[200000];
int main()
{
int i,j,m,n,t,sum,len,max;
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
{
scanf("%d%d",s+i,&t);
s[i]-=t;
s[n+i]=s[i];
}
max=sum=len=0;
m=n*2;
for(i=1;i<=m;i++)
{
sum+=s[i];
if(sum<0)
{
len=0;
sum=0;
continue;
}
len++;
if(len>max)
{
max=len;
if(max>=n)
break;
}
}
printf("%d\n",max);
}
}
/*
HOJ 1505 City Game
DP.一开始真心没想到，原来和1506是一样的。。。即每行选取最大面积矩形，大于最大则更新。
*/
#include <iostream>
using namespace std;
int h[1002],l[1002],r[1002];
int main()
{
char s[100];
int cas,i,j,m,n,ans,k,t;
cin>>cas;
while(cas--)
{
scanf("%d%d",&n,&m);
ans=0;
memset(h,0,4*(m+2));
for(i=0;i<n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%s",s);
if(s[0]=='F')
h[j]++;
else
h[j]=0;
}
h[0]=h[m+1]=-1;
for(j=1;j<=m;j++)
{
k=j-1;
while(h[k]>=h[j])
k=l[k];
l[j]=k;
}
for(j=m;j>0;j--)
{
k=j+1;
while(h[k]>=h[j])
k=r[k];
r[j]=k;
}
for(j=1;j<=m;j++)
{
t=(r[j]-l[j]-1)*h[j];
if(ans<t)
ans=t;
}
}
printf("%d\n",ans*3);
}
}
/*
HOJ 1506 Largest Rectangle in a Histogram
动态规划
查找边界时可以保存当前边界值，可以方便下次的边界查找。
另外有注意的范围，用64位存储。
*/
#include <iostream>
using namespace std;
int l[100002],r[100002];
long s[100002];
int main()
{
int i,j,n;
__int64 max,t;
while(scanf("%d",&n)&&n)
{
for(i=1;i<=n;i++)
scanf("%ld",s+i);
max=0;
s[0]=s[n+1]=-1;
for(i=1;i<=n;i++)
{
j=i-1;
while(s[i]<=s[j])
j=l[j];
l[i]=j;
}
for(i=n;i>0;i--)
{
j=i+1;
while(s[i]<=s[j])
j=r[j];
r[i]=j;
}
for(i=1;i<=n;i++)
{
t=(__int64)(r[i]-l[i]-1)*s[i];
if(max<t)
max=t;
}
printf("%I64d\n",max);
}
}
/*
HOJ 1864 最大报销额
01背包问题
*/
#include <iostream>
using namespace std;
int s[3000001];
int main()
{
char a,b;
double t,sum,money[3];
int up,i,j,n,m,flag,max,temp;
while(~scanf("%lf%d",&t,&n)&&n)
{
up=(int)(t*100);
memset(s,0,sizeof(s));
s[0]=1;
max=0;
for(i=0;i<n;i++)
{
sum=0;
money[0]=money[1]=money[2]=0;
flag=1;
scanf("%d",&m);
for(j=0;j<m;j++)
{
scanf("%c%c%c%lf",&b,&a,&b,&t);
if(flag)
{
if(a>'C'||a<'A'||t>600)
flag=0;
else
{
money[a-'A']+=t;
sum+=t;
if(sum>1000||money[a-'A']>600)
flag=0;
}
}
}
if(flag)
for(j=max;j>=0;j--)
if(s[j])
{
s[temp=j+(int)(sum*100)]=1;
if(temp>max&&temp<=up)
max=temp;
}
}
printf("%d.%02d\n",max/100,max%100);
}
}
/*
HOJ 2059 龟兔赛跑
*/
#include <iostream>
using namespace std;
int main()
{
int i,j,n,L,t,c,vr,vc,vt,s[102];
double up,m,Min,d[102],len;
while(~scanf("%d",&L))
{
scanf("%d%d%d%d%d%d",&n,&c,&t,&vr,&vc,&vt);
for(i=1;i<=n;i++)
scanf("%d",s+i);
s[++n]=L;
up=(L*1.0)/vr;
m=0;
d[0]=s[0]=0;
for(i=1;i<=n;i++)
{
Min=0x7FFFFFFF;
for(j=0;j<i;j++)
{
len=s[i]-s[j];
m=c>len?(1.0*len/vc):(1.0*c/vc+1.0*(len-c)/vt);
m+=d[j];
if(j)
m+=t;
if(Min>m)
Min=m;
}
d[i]=Min;
}
if(d[n]>up)
printf("Good job,rabbit!\n");
else
printf("What a pity rabbit!\n");
}
}
/*
HOJ 2159 FATE
二维01背包
*/
#include <iostream>
using namespace std;
int v[101],c[101],dp[101][101];
int n,m,k,s,t;
void tpack(int cost1,int cost2,int weight)
{
for(int i=cost1;i<=m;i++)
for(int j=cost2;j<=s;j++)
if(dp[i][j]<(t=dp[i-cost1][j-cost2]+weight))
dp[i][j]=t;
}
int main()
{
while(cin>>n>>m>>k>>s)
{
memset(dp,0,sizeof(dp));
for(int i=0;i<k;i++)
{
cin>>v[i]>>c[i];
tpack(c[i],1,v[i]);
}
if(dp[m][s]<n)
{
cout<<-1<<endl;
continue;
}
int min=0x7FFFFFFE;
for(int i=0;i<=m;i++)
for(int j=0;j<=s;j++)
if(dp[i][j]>=n&&min>i)
min=i;
cout<<m-min<<endl;
}
}
/*
HOJ 2577 How to Type
*/
#include <iostream>
using namespace std;
int on[101],off[101];
char s[100];
inline int min(int a,int b)
{
return a<b?a:b;
}
int main()
{
int i,len,cas;
cin>>cas;
while(cas--)
{
scanf("%s",s);
on[0]=off[0]=2;
if(s[0]>='a')
off[0]=1;
len=strlen(s);
for(i=1;i<len;i++)
{
if(s[i]>='a')
{
on[i]=min(on[i-1]+2,off[i-1]+2);
off[i]=min(on[i-1]+2,off[i-1]+1);
}
else
{
on[i]=min(on[i-1]+1,off[i-1]+2);
off[i]=min(on[i-1]+2,off[i-1]+2);
}
}
printf("%d\n",min(on[i-1]+1,off[i-1]));
}
}
/*
HOJ 2830 Matrix Swapping II
求正数的最大值就是求负数的最小值。。。这样写貌似比较简洁
*/
#include <iostream>
#include <algorithm>
using namespace std;
char str[1001];
int s[1001],a[1001];
int cmp(const void* a,const void* b)
{
return *(int *)a-*(int *)b;
}
int main()
{
int m,n,i,j,t,min;
while(~scanf("%d%d",&n,&m))
{
for(j=0;j<=m;j++)
s[j]=0;
min=0;
for(i=1;i<=n;i++)
{
scanf("%s",str+1);
for(j=1;j<=m;j++)
if(str[j]=='0')
s[j]=0;
else
s[j]--;
for(j=1;j<=m;j++)
a[j]=s[j];
qsort(a+1,m,sizeof(int),cmp);
for(j=1;j<=m;j++)
if(min>(t=j*a[j]))
min=t;
}
printf("%d\n",-min);
}
}
/*
HOJ 2844 Coins
*/
#include <iostream>
using namespace std;
int c[101],v[101],dp[100001],num[101],V;
inline int max(int a,int b)
{
return a>b?a:b;
}
void zpack(int cost,int weight)
{
for(int i=V;i>=cost;i--)
dp[i]=max(dp[i],dp[i-cost]+weight);
}
void cpack(int cost,int weight)
{
for(int i=cost;i<=V;i++)
dp[i]=max(dp[i],dp[i-cost]+weight);
}
void mpack(int cost,int weight,int amount)
{
if(amount*cost>=V)
{
cpack(cost,weight);
return;
}
for(int k=1;k<amount;k*=2)
{
amount-=k;
zpack(cost*k,weight*k);
}
zpack(cost*amount,weight*amount);
}
int main()
{
int i,j,n,ans;
while(scanf("%d%d",&n,&V),n|V)
{
ans=0;
for(i=0;i<=V;i++)
dp[i]=0;
for(i=0;i<n;i++)
scanf("%d",v+i);
for(i=0;i<n;i++)
scanf("%d",num+i);
for(i=0;i<n;i++)
mpack(v[i],v[i],num[i]);
for(i=1;i<=V;i++)
if(dp[i]==i)
ans++;
printf("%d\n",ans);
}
}
/*
HOJ 2845 Beans
搬寝室的平方。。。每次取每行最大和，最后取每列的最大和
*/
#include <iostream>
using namespace std;
int a[200001],b[200001];
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int m,n,i,j,t;
a[0]=0;
while(~scanf("%d%d",&n,&m))
{
for(i=1;i<=n;i++)
{
scanf("%d",a+1);
for(j=2;j<=m;j++)
{
scanf("%d",&t);
a[j]=max(a[j-2]+t,a[j-1]);
}
b[i]=a[m];
}
a[1]=b[1];
for(i=2;i<=n;i++)
a[i]=max(a[i-2]+b[i],a[i-1]);
printf("%d\n",a[n]);
}
}
/*
HOJ 2870 Largest Submatrix
3 X CityGames.记录a，b，c三个数组，每次查找边界求最大面积。
*/
#include <iostream>
using namespace std;
int ch[3][1001],l[1001],r[1001];
int main()
{
char s[1001];
int m,n,i,j,k,h,Max,t;
while(~scanf("%d%d",&n,&m))
{
Max=0;
for(i=0;i<=m;i++)
ch[0][i]=ch[1][i]=ch[2][i]=0;
for(i=1;i<=n;i++)
{
scanf("%s",s+1);
for(j=1;j<=m;j++)
{
switch(s[j])
{
case 'a':
{
ch[0][j]++;
ch[1][j]=0;
ch[2][j]=0;
break;
}
case 'b':
{
ch[0][j]=0;
ch[1][j]++;
ch[2][j]=0;
break;
}
case 'c':
{
ch[0][j]=0;
ch[1][j]=0;
ch[2][j]++;
break;
}
case 'w':
{
ch[0][j]++;
ch[1][j]++;
ch[2][j]=0;
break;
}
case 'x':
{
ch[0][j]=0;
ch[1][j]++;
ch[2][j]++;
break;
}
case 'y':
{
ch[0][j]++;
ch[1][j]=0;
ch[2][j]++;
break;
}
case 'z':
{
ch[0][j]++;
ch[1][j]++;
ch[2][j]++;
break;
}
}
}
for(h=0;h<3;h++)
{
ch[h][0]=ch[h][m+1]=-1;
for(j=1;j<=m;j++)
{
k=j-1;
while(ch[h][k]>=ch[h][j])
k=l[k];
l[j]=k;
}
for(j=m;j>=1;j--)
{
k=j+1;
while(ch[h][k]>=ch[h][j])
k=r[k];
r[j]=k;
}
for(j=1;j<=m;j++)
{
if(Max<(t=(r[j]-l[j]-1)*ch[h][j]))
Max=t;
}
}
}
printf("%d\n",Max);
}
}