本文共 904 字,大约阅读时间需要 3 分钟。
1573 88 1 0 2 7 4 44 5 2 6 5
30
代码:
#include<cstdio>
#include<algorithm> #include<cstring> #include<queue> #include<map> #include<set> typedef long long LL; const int maxn=105; using namespace std; int main() { int i,j,n,t; int dp[maxn][maxn],a[maxn][maxn]; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=i;j++) { scanf("%d",&a[i][j]); } } memset(dp,0,sizeof(dp)); for(j=1;j<=n;j++) dp[n][j]=a[n][j];//边界问题,将行赋值给dp数组 for(i=n-1;i>=1;i--)//一定是逆序枚举的 for(j=1;j<=i;j++) dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);//取左下右下较大着 printf("%d\n",dp[1][1]);//由于逆序枚举,所以答案是dp[1][1]; } return 0; }转载地址:http://sjncf.baihongyu.com/