Question

一道简单的ACM题，却总是MLE,都快疯了，帮忙解答一下

题目：http://acm.nankai.edu.cn/p1703.html

我用的内存也不多啊，就是一个队列，长度小于30，还有一个数组a[maxsize<=30]

我的代码：

#include <cstdlib>
#include <iostream>
#include<queue>
using namespace std;

int main(int argc, char *argv[])
{
int maxsize;
queue<int> q;
int num;
char ch;
int icnt = 1;
while(1)
{
cin>>num;
q.push(num);
if(num>maxsize)
maxsize = num;
ch = cin.get();
if(ch==EOF)
break;
}
long *a = new long[maxsize];
for(int i = 0; i<maxsize; i++)
{a[i] = 0;}
a[0] = a[1] = 1;
for(int i = 2; i<maxsize; i++)
{
for(int j = 0; j<i; j++)
{
a[i] += a[j]*a[i-1-j];
}

}
while(!q.empty())
{
cout<<"Case "<<icnt<<":"<<endl;
cout<<a[q.front()]<<endl;
icnt++;
q.pop();
}
delete []a;
//system("PAUSE");
return EXIT_SUCCESS;
}
#include <cstdlib>
#include <iostream>
#include<vector>
using namespace std;

int main(int argc, char *argv[])
{
int i,j;
vector <long long> f;
f.resize(31);
f[0] = 1;
for(i = 1; i<=30; i++)
{
for(j=0; j<i;j++)
{f[i] += f[j]*f[i-j-1];}
}
i = 0;
while(cin>>j)
{
i++;
cout<<"Case "<<i<<':'<<endl<<f[j]<<endl;
}
//system("PAUSE");
return EXIT_SUCCESS;
}

Answer 1

如果出现内存不够的情况，唯一的可能就是你的队列消耗掉了太多内存。0<n≤30，n其实对应的是你程序里的num，也就是说maxsize一定是小于等于30的。但q的长度跟测试数据数量有关，你根本没法保证q的长度小于30.
另外，你的计算过程太简单了。n等于30的话，结果肯定会远远超过int的表示范围。你需要实现高精度加法和乘法。
最好这么改：先把从1到30的结果都算出来，并保存到一个长度为30的数组里。结果都用字符串形式保存。然后每读入一个测试数据，就直接查表输出好了。

补充：
你改完后的答案应该是WA而不是MLE了吧？之前我都说了精度不够，long long也就是64位，够不够用其实你随便估算下就知道了。要改成字符串类型，然后自己用字符串类型实现高精度乘法和加法！

Answer 2

好吧，没注意n有范围的，试试是楼上的方法吧