资深光能
求大牛
@方亦欧 @王星河 @梁锦程 @陆麟瑞 @栾峻岩 @蒋志航
黄俊博在2018-07-08 09:23:50追加了内容
#include<iostream>
#include<cmath>
using namespace std;
int a[200];
int f[10000];
int s;
int count;
void search(int n)
{
if(n==0)
{
count++;
return ;
}
for(int i=1;i<=sqrt(n);i++)
{
if(n>=a[i])
{
// cout<<n<<endl<<a[i]<<endl<<endl;
n-=a[i];
search(n);
n+=a[i];
}
}
}
int main()
{
int n;
for(int i=1;i<=181;i++)
a[i]=i*i;
cin>>n;
while(n--)
{
count=0;
cin>>s;
search(s);
cout<<count<<endl;
}
return 0;
}
本人写了下，超时，求大佬
黄俊博在2018-07-08 10:11:38追加了内容
我又改了下帮看
#include<iostream>
#include<cmath>
using namespace std;
int a[200];
int f[10000];
int s;
int last=1;
int total;
int count;
void search(int n)
{
if(total==4)return ;
if(n==0)
{
count++;
return ;
}
for(int i=1;i<=sqrt(n);i++)
{
if(n>=a[i] && total<4)
{
//last=i;
//cout<<n<<endl<<a[i]<<endl<<endl;
n-=a[i];
total++;
search(n);
n+=a[i];
total--;
}
}
}
int main()
{
int n;
for(int i=1;i<=181;i++)
a[i]=i*i;
cin>>n;
while(n--)
{
cin>>s;
search(s);
cout<<count<<endl;
count=0;
}
return 0;
}
黄俊博在2018-07-08 11:00:52追加了内容
我。。。又改了下
求大牛
#include<iostream>
#include<cmath>
using namespace std;
int a[200];
int f[10000];
int s;
int last=1;
int total;
int count;
void search(int n)
{
if(total==4)return ;
if(n==0)
{
count++;
return ;
}
for(int i=1;i<=sqrt(n);i++)
{
if(n>=a[i] && total<4)
{
//last=i;
//cout<<n<<endl<<a[i]<<endl<<endl;
n-=a[i];
total++;
search(n);
n+=a[i];
total--;
}
}
}
int main()
{
int n;
for(int i=1;i<=181;i++)
a[i]=i*i;
cin>>n;
while(n--)
{
cin>>s;
search(s);
cout<<count<<endl;
count=0;
}
return 0;
}
黄俊博在2018-07-08 11:01:50追加了内容
好吧其实没改
黄俊博在2018-07-08 11:10:46追加了内容
@贾文卓
不对
#include<iostream>
#include<cstring>
using namespace std;
int a[200];
int f[1000][1000];
int s;
int count;
int main()
{
int n;
cin>>n;
while(n--)
{
cin>>s;
memset(f,0,sizeof(0));
f[0][0]=1;
for(int i=1;i<=s;i++)
{
for(int j=1;j<=4;j++)
{
f[i][j]+=f[i-s][j-1];
}
}
cout<<f[n][1]+f[n][2]+f[n][3]+f[n][4];
}
return 0;
}
黄俊博在2018-07-08 11:16:50追加了内容
k怎么算呢
高级光能
这道题目是动态规划，而不是搜索。可以这样做：
设：f[i][j]表示将i表示成j个数的平方和形式的方案数。
状态转移方程：f[i][j]+=f[i-k][j-1]
边界：f[0][0]=1
解：f[n][1]+f[n][2]+f[n][3]+f[n][4]
k是一个平方数。
贾文卓在2018-07-08 16:39:41追加了内容
@黄俊博 这道题目用动态规划才方便，用暴力搜索会TLE，记忆化搜索我又不会。DP的部分程序：
f[0][0]=1;
for(k=0;k<a.size();k++)
for(i=a[k];i<=32768;i++)
for(j=1;j<=4;j++)
f[i][j]+=f[i-a[k]][j-1];
其中，a为动态数组，记录1~23768之间的完全平方数。
资深光能
有人么
缔造者之神
1
缔造者
1
修练者
这道题目是动态规划，而不是搜索。可以这样做：
设：f[i][j]表示将i表示成j个数的平方和形式的方案数。
状态转移方程：f[i][j]+=f[i-k][j-1]
边界：f[0][0]=1
解：f[n][1]+f[n][2]+f[n][3]+f[n][4]
k是一个平方数。
@黄俊博 这道题目用动态规划才方便，用暴力搜索会TLE，记忆化搜索我又不会。DP的部分程序：
f[0][0]=1;
for(k=0;k<a.size();k++)
for(i=a[k];i<=32768;i++)
for(j=1;j<=4;j++)
f[i][j]+=f[i-a[k]][j-1];
其中，a为动态数组，记录1~23768之间的完全平方数。
