HOJ 동적 계획 AC 코드 팩
112841 단어 동적 계획
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<<":
"<<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
",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:
My king, at most %d road",cas++,max);
if(max-1)
printf("s");
printf(" can be built.
");
}
}/*
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.
",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:
Can",cas++);
if(!flag)
printf("'t");
printf(" be divided.
");
}
}/*
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
",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
",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
",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.
");
else
printf("The minimum amount of money in the piggy-bank is %d.
",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
",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
",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
",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
",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#
",k++);
printf("points : %d
",d[n]);
printf("circuit : ");
print(line[n]);
printf("->1
");
if(cas)
printf("
");
}
}/*
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
",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
",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
",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
",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
",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!
");
else
printf("What a pity rabbit!
");
}
}/*
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
",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
",-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
",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
",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
",Max);
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
124. 두 갈래 나무의 최대 경로와 leetcode비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다. 본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
