Mike 有一个 N 行 N 列的方格矩阵。
位于第 i 行第 j 列的方格的位置坐标表示为 (i,j)。矩阵左上角方格的坐标即为 (1,1)。每个方格中都包含一定数量的硬币，Mike 只有到达一个方格内时，方可收集方格中的硬币。Ci,j 表示第 i 行第 j 列的方格中的硬币数量。
当 Mike 处于方格 (i,j) 时，他可以选择移动至方格 (i−1,j−1) 或方格 (i+1,j+1) 中，前提是所选择的方格位于矩阵边界内，且之前没有到达过。
Mike 可以选择从任意方格开始移动，也可以选择在移动至任意方格时结束移动。Mike 希望尽可能多的收集硬币。
请帮助他确定他可以收集的最大硬币数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<iostream>
using namespace std;
const int N=1010;
long long c[N][N];
long long n;
long long getans(int a,int b)
{
long long max=0;
while(a<=n&&b<=n)
{
max+=c[a][b];
a++,b++;
}
return max;
}
int main()
{
int T;
cin>>T;
for(int t=1;t<=T;t++)
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%lld",&c[i][j]);
long long ans = 0;
for(int i=1;i<=n;i++)
ans=max(ans,getans(i,1));
for(int i=1;i<=n;i++)
ans=max(ans,getans(1,i));
printf("Case #%d: %lld\n", t, ans);
}
return 0;
}
|
