一、dp水划分
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=55;
ll dp[maxn][maxn];
int main(void)
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(j==1||j==i)
{
dp[i][j]=1;
continue;
}
dp[i][j]+=dp[i-1][j-1];
if(i-j>=j) dp[i][j]+=dp[i-j][j];
}
}
ll ans=0;
for(int i=1;i<=n;i++)
ans+=dp[n][i];
printf("%lld\n",ans);
}
return 0;
}
二、没有重复次数限制的划分,其中n较大,不适合上一种解法:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#define ll long long
using namespace std;
const int mod=1000000007;
const int maxn=100010;
ll dp[maxn]={0};
void init(void)
{
dp[0]=1;
for(int i=1;i<=maxn-10;i++)
{
for(int j=1,r=1;i-(3*j*j-j)/2>=0;j++,r*=-1)
{
dp[i]=((dp[i]+dp[i-(3*j*j-j)/2]*r)%mod+mod)%mod;
if(i-(3*j*j+j)/2>=0)
dp[i]=((dp[i]+dp[i-(3*j*j+j)/2]*r)%mod+mod)%mod;
}
}
return ;
}
int main(void)
{
int t;
cin>>t;
init();
while(t--)
{
int n;
scanf("%d",&n);
printf("%lld\n",dp[n]);
}
return 0;
}
三、相同的数重复不能大于等于k个
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#define ll long long
using namespace std;
const int mod=1000000007;
const int maxn=100010;
int dp[maxn]={0};
int a[maxn],b[maxn];
void _init(void)
{
a[0]=0;
b[0]=0;
for(int x=1;x<=10000;x++)
{
a[x]=((3*x*x-x)/2);
b[x]=((3*x*x+x)/2);
}
}
void init(void)
{
dp[0]=1;
for(int i=1;i<=maxn-10;i++)
{
for(int j=1,r=1;i-a[j]>=0;j++,r*=-1)
{
dp[i]=(dp[i]+dp[i-a[j]]*r)%mod;
if(i-b[j]>=0)
dp[i]=(dp[i]+dp[i-b[j]]*r)%mod;
}
if(dp[i]<0) dp[i]+=mod;
}
return ;
}
int ***(int n,int k)
{
int ans=dp[n];
for(int j=1,r=-1;n-k*a[j]>=0;j++,r*=-1)
{
ans=(ans+dp[n-k*a[j]]*r)%mod;
if(n-k*b[j]>=0)
ans=(ans+dp[n-k*b[j]]*r)%mod;
}
return ans>=0?ans:(ans+mod);
}
int main(void)
{
int t;
scanf("%d",&t);
_init();
init();
while(t--)
{
int n,k;
scanf("%d%d",&n,&k);
printf("%d\n",***(n,k));
}
return 0;
}