C++14(g++5.4) 解法, 执行用时: 489ms, 内存消耗: 2488K, 提交时间: 2019-09-14 08:43:51

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int s, d, m;
	cin >> s >> d >> m;
	vector <vector <int>> a(s, vector <int> (d));
	for (int i = 0; i < s; ++i)
		for (int j = 0; j < d; ++j)
			cin >> a[i][j];
	for (int i = 1; i < d; ++i)
	{
		vector <int> f(500001);
		int earn = 0;
		for (int j = 0; j < s; ++j)
			for (int k = a[j][i - 1]; k <= m; ++k)
				earn = max(earn, f[k] = max(f[k], f[k - a[j][i - 1]] + a[j][i] - a[j][i - 1]));
		m += earn;
	}
	cout << m;
}

C++11(clang++ 3.9) 解法, 执行用时: 358ms, 内存消耗: 2660K, 提交时间: 2019-09-16 16:44:23

#include<bits/stdc++.h>
using namespace std;
int a[61][21],f[500005];
int main()
{
int s,d,m;
scanf("%d%d%d",&s,&d,&m);
for(int i=1;i<=s;i++)
{
for(int j=1;j<=d;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int k=2;k<=d;k++)
{
memset(f,0,sizeof(f));
int maxx=0;
for(int i=1;i<=s;i++)
{
for(int j=a[i][k-1];j<=m;j++)
{
f[j]=max(f[j],f[j-a[i][k-1]]+a[i][k]-a[i][k-1]);
maxx=max(f[j],maxx);
}
}
m+=maxx;

}
printf("%d",m); 
return 0;
}