| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
巧妙地转化时间复杂度问题,哎,少了一个大括号,害我r了那么多次//A*B=C,直接算得O(n3)话必然会超时,进而转化为X*A*B=X*C,X设成(1,2,3,...,n)就把问题转化为 O(n2)了,x矩阵用随机数,但是好像不用也可以过
#include "stdio.h"
main()
{
int i,j,n,flag=1;
long a[510][510],b[510][510],c[510][510],x[510]={0},x1[510]={0},x2[510]={0};
// long a[502][502],b[502][502],c[502][502],x[502]={0},x1[502]={0},x2[502]={0};
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%ld",&a[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%ld",&b[i][j]);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
scanf("%ld",&c[i][j]);
}
//x矩阵与a矩阵相乘
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
x[i]+=a[j][i]*j;
//求等式左边的x,a,b三个矩阵的积
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
x1[i]+=b[j][i]*x[j];
//求矩阵x,c的积
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
x2[i]+=c[j][i]*j;
for(i=1;i<=n;i++)
{
if(x1[i]!=x2[i])
{ flag=0;break;}
}
if(flag==1)
printf("YES\n");
else
printf("NO\n");
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator