题意:
基本整数划分问题
思路:
第一次接触生成函数问题,这个题目就是一个基础的生成函数问题.
我们构造生成函数为 （1+x+x^2+x^3....)(1+x^2+x^4+....).....(1+x^n) 用x来表示数,指数表示数的大小
解得x^n的系数即为所求.
#include<bits/stdc++.h>
#define Ri(a) scanf("%d", &a)
#define Rl(a) scanf("%lld", &a)
#define Rf(a) scanf("%lf", &a)
#define Rs(a) scanf("%s", a)
#define Pi(a) printf("%d\n", (a))
#define Pf(a) printf("%lf\n", (a))
#define Pl(a) printf("%lld\n", (a))
#define Ps(a) printf("%s\n", (a))
#define W(a) while(a--)
#define CLR(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define exp 0.00000001
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int ans1[200];
int ans2[200];
int n;
int main()
{
while(~Ri(n))
{
for(int i=0;i<=n;i++)
{
ans1[i]=1;
ans2[i]=0;
}
for(int i=2;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
for(int k=0;k+j<=n;k+=i)
{
ans2[k+j]+=ans1[j];
}
}
for(int j=0;j<=n;j++)
{
ans1[j]=ans2[j];
ans2[j]=0;
}
}
Pi(ans1[n]);
}
return 0;
}
这个题目也可以用dp来做.
定义dp[i][j]表示对于i,用不超过j的数来划分,一共有几种划分方式.
那么当i==j dp[i][j]=dp[i][j-1]+1 这个+1 其实就是i本身对自己的划分,
i<j 这个情况下是不可能的,dp[i][j]=dp[i][i]
i>j 这个情况下 dp[i][j]=dp[i][j-1]+dp[i-j][j] (这时候就有两种选择,用j来划分和不用j来划分,
dp[i][j-1]表示 i 用不超过j-1的划分,即不用j来划分.dp[i-j][j] 表示用j来划分,当用j来划分时,j是确定的,剩下的就是i-j,这些用j来划分的种类数)
#include<bits/stdc++.h>
#define Ri(a) scanf("%d", &a)
#define Rl(a) scanf("%lld", &a)
#define Rf(a) scanf("%lf", &a)
#define Rs(a) scanf("%s", a)
#define Pi(a) printf("%d\n", (a))
#define Pf(a) printf("%lf\n", (a))
#define Pl(a) printf("%lld\n", (a))
#define Ps(a) printf("%s\n", (a))
#define W(a) while(a--)
#define CLR(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define exp 0.00000001
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
ll dp[200][200];
void init()
{
for(int i=1;i<200;i++)
dp[i][1]=dp[1][i]=dp[0][i]=1;
for(int i=2;i<200;i++)
{
for(int j=1;j<200;j++)
{
if(i<j)
dp[i][j]=dp[i][i];
if(i==j)
dp[i][j]=dp[i][j-1]+1;
if(i>j)
dp[i][j]=dp[i][j-1]+dp[i-j][j];
}
}
return ;
}
int main()
{
init();
int n;
while(~Ri(n))
{
Pl(dp[n][n]);
}
return 0;
}
这个题还可以用完全背包水过去,将1---n的所有数看成物品,然后跑一次背包.最后求满包dp[n],有几种就可以了.
#include<bits/stdc++.h>
#define Ri(a) scanf("%d", &a)
#define Rl(a) scanf("%lld", &a)
#define Rf(a) scanf("%lf", &a)
#define Rs(a) scanf("%s", a)
#define Pi(a) printf("%d\n", (a))
#define Pf(a) printf("%lf\n", (a))
#define Pl(a) printf("%lld\n", (a))
#define Ps(a) printf("%s\n", (a))
#define W(a) while(a--)
#define CLR(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define exp 0.00000001
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
ll dp[200];
int n;
int main()
{
while(~Ri(n))
{
CLR(dp,0);
dp[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
dp[j]+=dp[j-i];//i对j有贡献.
}
Pi(dp[n]);
}
return 0;
}