很水的一个dp
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=100; int a[2*N+5][N+5],dp[2*N+5][N+5]; int main() { int T,n,i,j,ca=0; cin>>T; while(T--) { cin>>n; memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); for( i=1;i<=n;i++) for(j=1;j<=i;j++) cin>>a[i][j]; for(i=n+1;i<=2*n-1;i++) for(j=1;j<=2*n-i;j++) cin>>a[i][j]; for(i=1;i<=n;i++) { for(j=1;j<=i;j++) dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j]; } for(i=n+1;i<=2*n-1;i++) { for(j=1;j<=2*n-i;j++) dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+a[i][j]; } ca++; cout<<"Case "<<ca<<": "<<dp[2*n-1][1]<<endl; } return 0; }