Problem #1009 - ECNU Online Judge

5 年，9 月前

include

using namespace std;
int main()
{
int ans[105][105];//以表格记录答案
for(int n=1;n<105;n++)
ans[n][1]=1;//n表示被拆分的正整数
for(int m=1;m<105;m++)
ans[1][m]=1;//m表示拆分结果可取的最大数
for(int n=2;n<105;n++)
for(int m=2;m<105;m++)
{
if(m>n) ans[n][m]=ans[n][n];//m过大时与m=n无异
else if(n==m) ans[n][m]=ans[n][m-1]+1;//n=m时，分最大值是否为m两种
else ans[n][m]=ans[n][m-1]+ans[n-m][m];//n>m时，分最大值是否为m两种
}

int n;
while(cin>>n) cout<<ans[n][n]<<endl;

}

回复 2 0

改个名字吧

5 年，9 月前

具体分析方法见百度百科

回复 1 0

10175102141

6 年，9 月前

大哥喝冰阔落

回复 0 0

MasterKiller

6 年，9 月前

母函数法吧，传统dp复杂度太高（n^2)。
此处Shut down MasterX 记录

回复 3 1

Master X

6 年，9 月前

不好意思我还真会母函数，谢谢提醒啊。

回复 1 0

爱丽丝_青贝尔克

6 年，9 月前

大哥抽中华

回复 1 0

13627999316

4 年，7 月前

#include <bits/stdc++.h>
using namespace std;
int a[1001];
bool vis[30];
int n,ans;

void dfs(int num,int cnt)   //cnt当前拆分中的数量+1。 
{
    if(num == 0) {      //拆分完毕 
        ans++;
        return;
    }
    for(int i = 1; i <= num; i++) {     //搜索进行拆分，拆分的一定要大于等于前一个数 
        if(i >= a[cnt-1]) {     //关键在这里 
            a[cnt] = i;
            num-=i;
            dfs(num,cnt+1);
            num+=i;     //回溯 
        }
    }
}

int main()
{
    while(cin>>n) {
        ans = 0;
        dfs(n,1);       //从1开始搜索方便第一个元素的搜索判断 
        cout<<ans<<endl;
    }
    return 0;
}

暴搜跪了。。。

回复 0 0

Canis

4 年，3 月前

你的a数组都没有初始化，怎么搜？

回复 0 0

LzQuarter

6 年，2 月前

stdio.h
int arr[105][105] = {0};
int dp(int remain, int up){
if(remain < 0)return 0;
if(arr[remain][up] != 0){
return arr[remain][up];
}
else{
int sum = 0;
for(int i = up; i > 0; i–){
sum += dp(remain - i, i);
}
arr[remain][up] = sum;
return sum;
}
}
int main(){
for(int i = 0; i < 105; i++){
arr[0][i] = 1;
}
int n;
while(scanf(“%d”, &n) != EOF){
printf(“%d\n”, dp(n, n));
}
return 0;
}
// remain 当前数字还剩余的未被分解的成分
// up 当前可用于分解余部的数字的上界
// 搜索过程每一层尝试剥离一个因子，同时规定新的因子上界
// 注意使用存储空间来缓存已经计算过的状态，避免重复计算

回复 0 0

10175101178

3 年，6 月前

include

int main()//动态规划超级简单
{
int n;
while(scanf(“%d”,&n)!=EOF){
int dp[101]={0};
dp[0]=1;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
dp[j]=(dp[j]+dp[j-i]);
printf(“%d\n”,dp[n]);
}
}

回复 0 0

cd106224

4 年，7 月前

//状态 dp[i][j]表示以j为最大值分解i的最多个数
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 105;
int dp[maxn][maxn];

int main() {
    fill(dp[0], dp[0] + maxn * maxn, 0);
    for (int i = 1; i < maxn; ++i) {
        for (int j = 1; j < maxn; ++j) {
            if (i == 1 || j == 1) {
                dp[i][j] = 1;
            }
        }
    }
    for (int i = 1; i < maxn; ++i) {
        for (int j = 1; j < maxn; ++j) {
            if (j > i) {
                dp[i][j] = dp[i][j - 1];
            }
            else if (i == j) {
                dp[i][j] = dp[i][j - 1] + 1;
            }
            else {
                dp[i][j] = dp[i - j][j] + dp[i][j - 1];
            }
        }
    }
    int n;
    while (cin >> n) {
        cout << dp[n][n] << endl;
    }
    return 0;
}

回复 0 0

1009. 整数的拆分

include

include

include

服务

开源

关于我们