3029. 不重复正整数

Andrew-Malcom

include

using namespace std;
int sum=0;
void dfs(int n,int m)
{
        if(n==0) sum++;
        else if(n<0) return;
        else{
                for(int i=m;i>=1;i--){
                        dfs(n-i,i-1);
                }
        }
}
int main()
{
        int t;cin>>t;
        for(int i=0;i<t;i++){
                sum=0;
                int n,m;cin>>n>>m;
                printf("case #%d:\n",i);
                dfs(n,m);
                cout<<sum<<endl;
        }
}
10175102262 LarsPendragon

没想到01背包,直接手动搞得其他方法。我的想法应该还是十分麻烦的。首先f(x,y)表示x不大于y的拆分,则f(x,y)可以分解成为f(x,y-1)+最大拆分为y的个数。最大拆分为y的个数可以表示为f(x-y,y-1),然后动态规划就可以了。
附C代码:

#include <stdio.h>
int main()
{
    int ans[51][21], i, j, k, x, ma;
    for(i=0; i<51; i++) for(j=0; j<21; j++) ans[i][j]=0;
    for(i=1; i<51; i++)
    {
        if(i>20) ma=20;
        else ma=i;
        for(j=1; j<=ma; j++)
        {
            x=i;
            if(j) ans[i][j]+=ans[i][j-1];
            if(i<21 && j==i) {ans[i][j]++; break;}
            k=j;
            x-=k--;
            if(x>19)
            {
                            while(x-k<k)
                            {
                                ans[i][j]+=ans[x-k][k];
                                k--;
                            }
                        }
            ans[i][j]+=ans[x][k];
        }
        if(ma<20) for(j=ma; j<21; j++) ans[i][j]=ans[i][ma];
    }
    int T, I, n, m;
    scanf("%d",&T);
    for(I=0; I<T; I++)
    {
        scanf("%d %d",&n,&m);
        printf("case #%d:\n%d\n",I,ans[n][m]);
    }
    return 0;
}
Cuibaby

include

using namespace std;
int n,m;
int ans=0;
void dfs(int i,int sum)
{
if(sum==n)
{
ans++;
return;
}
if(i>m||sum>n)
return;
dfs(i+1,sum+i);
dfs(i+1,sum);
}
int main()
{
int t;
cin>>t;
for(int i = 0; i < t; i++)
{
cin>>n>>m;
ans=0;
dfs(1,0);
printf(“case #%d:\n”,i);
cout<<ans<<endl;
}
return 0;
}

Li Dao

应该有简单的方法,不过我用的是01背包
那题是EOJ3034

Li Dao

应该有简单的方法,不过我用的是01背包

include

using namespace std;
int T,n,m;
int dp[60];
void solve()
{
cin>>n>>m;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=m;i++)
for(int j=n;j>=i;j–)
dp[j]+=dp[j-i];
cout<<dp[n]<<endl;
}
int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

for(int j=n;j>=i;j–)注意这层循环是倒着枚举的,否则这个数就可以取多遍了

记得有一题,是把一个数分解成2的幂加起来,方法也类似,题号记不得了,但就是EOJ上的题

Gino_Hong

搜索加剪枝水过去就完事儿了hh

include

using namespace std;
int n,m,ans;
void dfs(int pre,int sum){
if(sum>n) return;
if(sum==n){
ans++;
return;
}
for(int i=pre+1;i<=m;i++)
dfs(i,sum+i);
}
int main(void){
int t;
cin>>t;
for(int nt=0;nt>n>>m;
dfs(0,0);
cout<<ans<<endl;
}
}

Deuchie

[EOJ 3029] 不重复正整数

设 $dp(i, j)$ 表示用 1..=i 闭区间里的不重复正整数表示 $j$ 的方案数。一般情况下有两种选法:使用零数 $i$,然后用前 $i-1$ 个数字组成 $j-i$;或不使用零数 $i$,使用前 $i-1$ 个数字组成 $j$。这样得到了
$$
dp(i, j)=dp(i-1,j)+dp(i-1,j-i),j\ge i
$$

$$
dp(i,j)=dp(i-1,j),j<i
$$

(我没能捉摸明白 EOJ 的 cases 怎么用所以只能这样写 Math 公式了)

这样看来这其实就是一个背包问题。时间复杂度是 $O(\sum_{i=1}^tn_im_i)$。

#include "bits/stdc++.h"

using namespace std;
using u64 = uint64_t;

int main() {
    u64 t;
    cin >> t;
    for (u64 query = 0; query < t; ++query) {
        cout << "case #" << query << ":\n";
        u64 n, m;
        cin >> n >> m;
        vector<u64> dp(n + 1, 0);
        dp[0] = 1;
        for (u64 i = 1; i <= m; ++i) {
            for (u64 j = n; j >= i; --j) {
                dp[j] += dp[j - i];
            }
        }
        cout << dp[n] << '\n';
    }
}
playeroj

不知道为什么,不压减空间居然有问题了

Kevin_K

Hints:为什么会想到01背包?因为范围撑死了也就(20+1)*20/2=210。
Ps:在过五分钟语文就不能入场啦~

你当前正在回复 博客/题目
存在问题!