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