题目描述
摘花生(滚动数组版)(来自y总01背包的启发)
样例
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
int t;
int r,c;
int w[N][N];
int f[N];
int main()
{
cin>>t;
while(t--)
{
scanf("%d%d",&r,&c);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
scanf("%d",&w[i][j]);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
f[j]=max(f[j]+w[i][j],f[j-1]+w[i][j]);
cout<<f[c]<<endl;
memset(f,0,(c+1)*4);
}
}