这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=1284
粗略一看,直接套母函数的模版~~~ 结果TLE了:
// 注意这是TLE的代码
// HDOJ 1284
#include
using namespace std;
// Author: Tanky Woo
// www.wutianqi.com
const int _max = 40000;
int c1[_max], c2[_max];
int main()
{ //int n,i,j,k;
int nNum; //
int i, j, k;
while(scanf("%d", &nNum;) != EOF)
{
for(i=0; i<=nNum; ++i)
{
c1[i] = 1;
c2[i] = 0;
}
for(i=2; i<=3; ++i)
{
for(j=0; j<=nNum; ++j)
for(k=0; k+j<=nNum; k+=i)
{
c2[j+k] += c1[j];
}
for(j=0; j<=nNum; ++j)
{
c1[j] = c2[j];
c2[j] = 0;
}
}
printf("%d\n", c1[nNum]);
}
return 0;
}
后来改了下: 500多MS~~~
#include
using namespace std;
int c1[32768], c2[32768] = {0};
int main()
{
int i, j, k, h;
for (i = 0; i <= 32767; i++)
c1[i] = 1;
for (i = 2; i <= 3; i++)
{
for (j = 0; j <= 32767; j++)
{
for (k = 0; k + j <= 32767; k += i)
{
c2[k + j] += c1[j];
}
}
for (h = 0; h <= 32767; h++)
{
c1[h] = c2[h];
c2[h] = 0;
}
}
int n;
while (scanf("%d", &n;) != EOF)
printf("%d\n", c1[n]);
return 0;
}
后来发现这题其实可以不用母函数的: 思路: 直接COPY网上的了。 就是求2x+3y+k=m的问题这时m就可以写成m=6q+k; 带入上式子 可得到 y=3q+k/2-3x/2; x的取值0-2q之间的偶数 有1+q中 所以else后面要加1
#include
int main()
{
__int64 n,i,j,sum;
while(scanf("%I64d",&n;)==1)
{
sum=0;
for(i=0;i<=n/3;i++)
{
sum+=(n-i*3)/2+1;
}
printf("%I64d\n",sum);
}
}
最后一个,还是母函数的思想,但是时间是0MS~~~ AMB教主的代码~~~Orz
#include
using namespace std;
int num[32768];
void main()
{
int n,i;
num[0]=1;
for(i=1;i<32768;i++)
num[i]+=num[i-1];
for(i=2;i<32768;i++)
num[i]+=num[i-2];
for(i=3;i<32768;i++)
num[i]+=num[i-3];
while(cin>>n)
printf("%d\n",num[n]);
}