艺术联合会
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
艺术联合会顾名思义就是n个画家用n种颜色一起进行艺术创作（作画）。每一位画家仅使用一种颜色，并且规定n位画家使用的颜色是不同的，这里我们可以假设第一位画家使用的颜色编号为1，第2位画家使用的颜色编号为2以此类推。每一幅画上面都有n种颜色。我们假设把第j种颜色涂在第i幅画上需要消耗第j个画家的时间为 t[i][j]。
我们知道在任何情况下，规则都是至关重要的，因此画家们将根据以下规则进行作画：
1. 每一幅画都是由第一个画家先画，然后是第二个画家，然后是第三个画家……，也就是说，在第j个画家画完之后，一定是第(j + 1) 个画家进行作画 （如果有（j + 1）<= n)
2. 每一个画家在作画上按照这样的顺序进行作画：首先在第一幅画上作画，然后是第二幅画，依次类推直到第n幅画。
3. 不同的画家在不同的画幅上是可以同时工作的，比如说第二位画家在作第一幅画时，第一位画家可以作第二幅画。任何一个画家是不需要时间休息的。
4. 当第j个画家作完自己部分的画时，此幅画就立即可以被第(j + 1) 个画家使用。
假设第一位画家开始作画的时间是0，输出每一幅画被完成时的时间。
输入
第一行输入一个数T，表示有T组数据（1<=T<=100）。
每组数据第一行是两个整数：m 和 n（1 <= m <= 50000,1 <= n <= 5)m代表的是画幅的个数，n代表的是画家的个数。接下来每行有n个整数t[i][1],t[i][2]……t[i][n]（1 <= t[i][j] <= 1000),t[i][j] 表示第j个画家把第j种颜色涂在第i幅画上需要的时间。
输出
每组数据输出一行含有m个数 r1，r2，……rm，这里ri表示第i幅画被完成时的时间。
示例输入
2 5 1 1 2 3 4 5 4 2 2 5 3 1 5 3 10 1
示例输出
1 3 6 10 15 7 8 13 21
提示
来源
示例程序
#include<stdio.h>
#include<string.h>
int a[50000][6];
int b[50001],c[50001];
int main()
{
int T,n,m,i,j;
int p,r,pp;
int e;
scanf("%d",&T);
while(T--)
{
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=0;i<n;i++)
{
p = 0;
for(j=0;j<m;j++)
{
p = p + a[i][j];
}
b[i] = p + b[i-1];
}
for(i=1;i<n;i++)
{
for(j=0;j<m-1;j++)
{
pp = 0;
for(r=j+1;r<j+m;r++)
{
if(r<m)
{
pp = pp + a[i-1][r];
}
else
{
pp = pp + a[i][r-m];
}
}
pp = pp + c[j];
if(pp>=a[i][j])
{
c[j] = pp - a[i][j];
for(e=i;e<n;e++)
{
b[e] = b[e] - a[i][j];
}
}
else
{
c[j] = 0;
for(e=i;e<n;e++)
{
b[e] = b[e] - pp;
}
}
}
}
for(i=0;i<n;i++)
{
if(i<n-1)
{
printf("%d ",b[i]);
}
else
{
printf("%d\n",b[i]);
}
}
}
return 0;
}