杭电2391

其实这题是一道DP水题，一看就知道是数字三角变形来的。就是数字三角的思想只是变换了一点。

他是从左上方到右下方可以向右，向下，向右下（这个是不用考虑的）。最后求出最大的数字和。

这里和数字三角需要改变的一点就是我们事先要将最后一行加起来（这是压缩矩阵的方法，就是走过一行所有的数字之和）。

还有就是最后一列要单独说一下，因为他们后面没有了，不能再加后面的数，但是可以加上下面的数。

我开始想的有点复杂，但是有点懒代码没有改，用了两个数组。

#include
using namespace std;
int a[1005][1003];
int b[1005][1005];
int max(int n,int m)
{return n>m?n:m;
}
int main()
{int N;int r,c,i,j,k=0;cin>>N;while(N--){k++;cin>>r>>c;for(i=0;i<r;i++)for(j=0;j<c;j++){cin>>a[i][j];b[i][j]=a[i][j];}for(j=c-2;j>=0;j--)for(i=0;i<r;i++){a[i][j]+=a[i][j+1];}for(i=r-1;i>=0;i--)for(j=c-1;j>=0;j--){if(i==r-1)b[i][j]=a[i][j];else if(j==c-1){b[i][j]+=b[i+1][j];}else {b[i][j]+=max(b[i+1][j],b[i][j+1]);}}cout<<"Scenario #"<<k<<":"<<endl;cout<<b[0][0]<<endl;cout<<endl;}return 0;

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！