/*一个简单的滚动数组样例
滚动数组是dp中一种压缩空间的方法
二维数组从上向下的状态转移:
f[i][j]=max(f[i-1][j-1],f[i][j-1])+w[i][j]
我们在每次使用空间的时候只使用了两行
在算出f[i][0]到f[i][i]之间的数据后,f[i-1][0]这一行的数据就不再被使用了
我们希望能释放这些空间
既然每次只用两行,就把存储空间压缩到两行
具体做法:
i为偶数
f[i][1]=max(f[i-1][0],f[i][0])+w[i][1]
i为奇数
f[i][0]=max(f[i-1][1],f[i][1])+w[i][0]
进一步优化
把状态转移式子中的j-1替换成j:
f[i][j]=max(f[i-1][j],f[i][j])+w[i][j]
发现其实只用一行就够了
f[i]=max(f[i-1],f[i])+w[i]
从上向下遍历在最后输出之前需要找一轮最大值,花费O(n)的时间
所以用滚动数组会慢一些
第一次写题解,表达不清请见谅
下面是代码
文本框好像会把#识别成别的东西,以防万一
头文件是下面这两个
stdio.h 和 iostream(好像不用cin cout也行)
*/
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
int a[510],b[510];//a是滚动数组,b用来接收输入数据
int main(){
int n,sum=0;
cin>>n;
for(int i=1;i<=n;i){
for(int j=1;j<=i;j){
cin>>b[j];
}
//给的用例有负数,不能用a的初始值0,要处理边界值
a[i]=a[i-1]+b[i];
for(int j=i-1;j>1;j–){//倒过来遍历是因为a[j]用到左边的数a[j-1],要保证a[j]的更新在a[j-1]之前
a[j]=max(a[j],a[j-1])+b[j];
}
if(i!=1)
a[1]+=b[1];
}
for(int i=1;i<=n;i++)sum=max(sum,a[i]);
cout<<sum<<endl;
return 0;
}