首页 > 代码库 > hdu--4920--原来一直写了速度慢的矩阵乘法
hdu--4920--原来一直写了速度慢的矩阵乘法
这题....tle到落泪啊
后来 discuss里面的一个人 提供了一个链接 一下子 明白了 自己以前怎么没有注意过呢？
传送
然后 只要按照第二种写法 果然AC了... 虽然时间还是卡的很紧 但起码不是tle了
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int size = 810; 6 int x[size][size]; 7 int y[size][size]; 8 int z[size][size]; 9 10 int main()11 {12 cin.sync_with_stdio(false);13 int n , num;14 while( cin >> n )15 {16 memset( z , 0 , sizeof(z) );17 for( int i = 0 ; i<n ; i++ )18 {19 for( int j = 0 ; j<n ; j++ )20 {21 cin >> num;22 x[i][j] = num % 3;23 }24 }25 for( int i = 0 ; i<n ; i++ )26 {27 for( int j = 0 ; j<n ; j++ )28 {29 cin >> num;30 y[i][j] = num % 3;31 }32 }33 for( int i = 0 ; i<n ; i++ )34 {35 for( int k = 0 ; k<n ; k++ )36 {37 if( x[i][k] )38 {39 for( int j = 0 ; j<n ; j++ )40 {41 z[i][j] += x[i][k] * y[k][j];42 }43 }44 }45 }46 for( int i = 0 ; i<n ; i++ )47 {48 cout << (z[i][0]%3);49 for( int j = 1 ; j<n ; j++ )50 {51 cout << " " << (z[i][j]%3) ;52 }53 cout << endl;54 }55 }56 return 0;57 }
这边 还有一个很重要的判断
if( x[i][k] )
有没有这句话 时间差了300多Ms 因为这样一下子剪枝了很多不用进入for循环了
today:
我遇到猫在潜水 却没遇到你
我遇到狗在攀岩 却没遇到你
我遇到夏天飘雪 却没遇到你
我遇到冬天打雷 却没遇到你
我遇到所有的不平凡
却一直遇不到平凡的你
hdu--4920--原来一直写了速度慢的矩阵乘法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。