搜狗笔试--距离的总和,简单dp思路正确率43%,内存超限?
问题描述:
思路:
输入个数可能是几万个,每个偶数可能是几百万。暴力两两比较n(n-1)/2次是肯定不行的。
首先写一个计算偶数距离的函数int lenxy(int x, int y);
然后新建一个dp矩阵,只用下三角存储两两之间距离。
容易看出规律,dp[i][j] = dp[i-1][j] + dp[i][i-1],每次只要算出dp[i][i-1]就行了。
测试正确43%,内存超限。
改进:
考虑到dp矩阵本身可能是内存超限的原因,这里不建立dp矩阵,改为存储上一行的数据。每次循环更新上一行即可。
但是运行结果依然是
正确43%,内存超限。
改进前后源码差不多,下面是改进后的。写的很烂大家多指教,正确性应该是没问题的。内存超限问题出在哪儿,
怎么解决?
#include<iostream> #include<vector> using namespace std; bool isPrime(int x) { for(int i=2;i<x;i++) { if(x%i==0) return false; } return true; } int lenxy(int a,int b) { if(a>=b) return 0; int res=0; for(int i=a+1;i<b;i++) { if(isPrime(i)) { res++; } } return res; } int main() { int n; while(cin>>n) { vector<int> v; int t; for(int i=0;i<n;i++) { cin>>t; v.push_back(t); } vector<vector<int> > dp(n,vector<int>(n,0)); int res=0; vector<int> pre(1,0); for(int i=1;i<n;i++) { vector<int> tmp(i,0); int index=i-1; tmp[index]=lenxy(v[i-1],v[i]); res+=tmp[index]; index--; for(int j=i-2;j>=0;j--) { dp[i][j]=dp[i][i-1]+dp[i-1][j]; tmp[index]=tmp[i-1]+pre[index]; res+=tmp[index]; index--; } pre.swap(tmp);//更新前一行pre } cout<<res<<endl; } return 0; }
感谢北站匹诺曹给出数学归纳的公式,具体推导如下