xryjr233 @ 2017-05-30 09:15:13
我用了记忆化搜索依然TLE了QAQ，求优化
#include<bits/stdc++.h>
using namespace std;
int n,a[500510],sn[499510][2]={-1},siz=0,jy[500510];
int fs(int x){
if(jy[x]) return jy[x];
if(sn[x][0]<0) return a[x];
return jy[x]=max(a[x]+fs(sn[x][0]),a[x]+fs(sn[x][1]));
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
scanf("%d",&a[++siz]);
if(i!=n){
sn[siz][0]=siz+i;
sn[siz][1]=siz+i+1;
}
}
}
printf("%d",fs(1));
return 0;
}by xryjr233 @ 2017-05-30 09:20:41
89分了，这是重构后代码：
#include<bits/stdc++.h>
using namespace std;
int n,a[1010][1010],jy[1010][1010];
int fs(int x,int y){
if(jy[x][y]) return jy[x][y];
if(x==n) return a[x][y];
return jy[x][y]=max(a[x][y]+fs(x+1,y),a[x][y]+fs(x+1,y+1));
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
scanf("%d",&a[i][j]);
}
}
printf("%d",fs(1,1));
return 0;
}by xryjr233 @ 2017-05-30 09:28:04
过了，不用麻烦了谢谢