Hrbust1038 http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1038
1 //要注意的一点是数字的编号是J,J+1,J+2刚开始编号错误弄啦很久 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iostream> 5 #include<string.h> 6 using namespace std; 7 int ma[1005][1005],dp[1005][1005]; 8 int n; 9 int maxlen(int i,int j){ 10 if(dp[i][j]!=-1)return dp[i][j]; 11 if(i==n)return dp[i][j]=ma[i][j]; 12 return dp[i][j]=ma[i][j]+max(maxlen(i+1,j),max(maxlen(i+1,j+1),maxlen(i+1,j+2))); 13 } 14 int main() 15 { 16 int t; 17 cin>>t; 18 while(t--){cin>>n; 19 memset(dp,-1,sizeof(dp)); 20 memset(ma,0,sizeof(ma)); 21 for(int i=1;i<=n;i++){ 22 for(int j=1;j<=2*i-1;j++){ 23 cin>>ma[i][j]; 24 } 25 } 26 cout<<maxlen(1,1)<<endl; 27 } 28 }