题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
先取第一个人走过的最大值,再取第二人走过的最大值两个综合,结果错误, 因为题目求得是两个人走过采取的最大值,一个一个取会产生错误。
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 12;
int a[N][N];
int f[N][N];
int g[N][N];
int main()
{
int n;
cin >> n;
int x, y, c;
while(cin >> x >> y >> c, x || y || c)a[x][y] = c;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];
}
int res = f[n][n];
int j = n, i = n;
memcpy(g, a, sizeof g);
g[n][n] = 0;
cout << f[n][n] << endl;
while(i != 1 || j != 1)
{
if(j > 1)
{
if(f[i][j] == f[i][j - 1] + a[i][j])
j --;
else i --;
}
else i --;
g[i][j] = 0;
cout << i << ' ' << j << endl;
}
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + g[i][j];
res += f[n][n];
cout << res << endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度分析:blablabla
C++ 代码
blablabla