Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

巧妙地转化时间复杂度问题,哎,少了一个大括号,害我r了那么多次

Posted by 1008061011 at 2011-08-08 21:20:18 on Problem 3318
//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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator