ural 1869. New Year Cruise
|
描述：从Vladivostok站Moscow站共有n个站台，Vladivostok记为1，Moscow记为n，火车来回往返。现在给出从车站i到车站j和j到i的买票人数，计算需要的最少节车厢。
思路：水题，模拟即可。注意先下后上，用一个max保持最大的人数。
代码：
//g++ 4.7.2 用到了变长数组
#include
int main()
{
int n;
scanf("%d", &n);
int a[n+1][n+1];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
scanf("%d", &a[i][j]);
int max = 0, sum = 0;
for (int i = 1; i <= n; ++i)
{
for (int t = 1; t < i; ++t)
sum -= a[t][i];
for (int j = i + 1; j <= n; ++j)
{
sum += a[i][j];
if (sum > max)
max = sum;
}
}
sum = 0;
for (int i = n; i >= 1; --i)
{
for (int t = n; t > i; --t)
sum -= a[t][i];
for (int j = i - 1; j >= 1; --j)
{
sum += a[i][j];
if (sum > max)
max = sum;
}
}
printf("%d\n", max % 36 == 0 max / 36 : max / 36 + 1);
return 0;
}
|