题解

245 条题解

  • 13
    @ 2017-05-08 08:56:40
    /*
    经典DP了
    将整数i分成j份,对1进行讨论
    若每份都大于1,即先将i分出j来使每份为1,问题转化为将剩下的i-j分成j份的问题
    若至少有一份为1,1已经占了一份,问题转化为将i-1分成j-1份的问题
    设f[i][j]表示数i分成j份的划分方案数
    可得f[i][j]=f[i-j][j]+f[i-1][j-1]
    然后两个顺序递推就好了 初值f[0][0]=1 f[i][1]=1
    这个第一个转移有点难理解啊
    其实就是我们i分成j份
    如果不包含1即每份都大于1   即每个拆出来的数都可以表示为x+1
    所以我们相当于每个数加上了一个1上去
    这样就完成了一个状态的转移
    注意i>=j 因为不可能分的份数比自己还多OTZ
    然后就推出来了
    然后你就AC了此题
    */
    #include <cstdio>
    using namespace std;
    
    int f[210][7];
    int n,k,i,j;
    
    int main()
    {
        scanf("%d%d",&n,&k);
        f[0][0]=1;
        for(i=1;i<=n;i++)
            f[i][1]= 1;
        for(i=1;i<=n;i++)
            for(j=1;j<=k;j++)
                if(i>=j)
                    f[i][j]=f[i-j][j]+f[i-1][j-1];
        printf("%d\n",f[n][k]);
        return 0;
    }
    
  • 9
    @ 2013-11-05 21:50:11

    var
    n,k,i,j:longint;
    f:array[-200..200,-200..6]of longint;
    begin
    readln(n,k);
    f[1,1]:=1;
    for i:=2 to n do
    for j:=1 to k do
    f[i,j]:=f[i-1,j-1]+f[i-j,j];
    writeln(f[n,k]);
    end.
    1. 解释一下DP方程
    假设有4个数字,a,b,c,d
    为了使状态不重复,所以,有俩种可能推到当前状态
    1.在原来有序的基层上在前面加上一个1,即f[i,j]:=f[i-1,j-1]
    2.在原来有序的基层上,集体都增加1,即f[i-j,j];(当前有j个数字)
    这样可以始终保证序列有序,并且不会重复

    • @ 2015-10-31 18:55:11

      看了那么多题解,就你的看懂了。。。

    • @ 2016-05-28 23:02:55

      就你的看懂了.. 赞一个

    • @ 2016-06-14 15:48:24

      这个一看就懂,谢谢哈哈

    • @ 2017-03-05 17:27:15

      赞!

  • 3
    @ 2017-07-18 23:16:50

    Method 1:DP

    #include<cstdio>
    #include<iostream>
    
    using namespace std;
    
    int n, k, ans = 0;
    
    int dp[201][7];
    int main(){
        scanf("%d%d", &n, &k);
        for(int i = 0; i <= n; i++) dp[i][1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 2; j <= min(i, k); j++){
                dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
            }
        }
        printf("%d", dp[n][k]);
        return 0;
    }
    

    Method 2:dfs枚举

    #include<cstdio>
    #include<iostream>
    
    using namespace std;
    
    int n, k, ans = 0;
    
    void dfs(int val, int am, int last){
        if(am == k){
            if(val == n)    ans++;
            return;
        }
        for(int i = last; i <= n-val; i++)
            dfs(val+i, am+1, i);
    }
    
    int main(){
        scanf("%d%d", &n, &k);
        dfs(0, 0, 1);
        printf("%d", ans);
        return 0;
    }
    
  • 2
    @ 2022-08-15 10:38:11
    #include<bits/stdc++.h>
    using  namespace std;
    typedef long long ll;
    const ll N=50005;
    ll i,j=0,m,n,k=0;
    void yy(ll m,ll n)
    {
        if(m==n||n==1)
        {
            k++;
            if(n==1)
            return;
            yy(m,n-1);
        }
        else
        {
            if(m<n)
                yy(m,m);
            else
            {
                yy(m-n,n);
                yy(m,n-1);
            }
        }
    }
    void xx(ll m,ll n)
    {
        if(m==n)
        {
            k++;
            return;
        }
        else
            yy(m-n,n);
    }
    int main()
    {
        cin>>m>>n;
        xx(m,n);
        cout<<k;
        return 0;
    }
    

    //递归也能做:)

  • 2
    @ 2016-07-16 11:02:17

    数据比较水估计搜索递归也能过。
    DP做法:
    将整数i分成j份,对1进行讨论
    若每份都大于1,即先将i分出j来使每份为1,问题转化为将剩下的i-j分成j份的问题
    若至少有一份为1,1已经占了一份,问题转化为将i-1分成j-1份的问题
    设f[i][j]表示数i分成j份的划分方案数,可得f[i][j]=f[i-j][j]+f[i-1][j-1]
    ~~~
    #include <cstdio>
    int n,k,f[205][8];
    int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) f[i][1]=1;
    for(int i=2;i<=n;i++)
    for(int j=2;j<=k&&j<=i;j++)
    f[i][j]=f[i-1][j-1]+f[i-j][j];
    printf("%d\n",f[n][k]);
    return 0;
    }

  • 2
    @ 2015-03-25 18:06:38

    感谢楼下的楼下给的小提示。递归比较好理解- -
    ###block code
    program ex;
    var n,k:longint;
    ans:int64;
    procedure main(x,y,z:longint);
    var num,i:longint;
    begin
    num:=x div y;
    if y=1 then
    begin
    inc(ans); exit;
    end;

    for i:=z to num do
    begin
    main(x-i,y-1,i);
    end;
    end;

    begin //main
    read(n,k); ans:=0;
    main(n,k,1);

    write(ans);
    end.

  • 1
    @ 2018-01-03 14:45:39
    #include<cstdio>
    int a[210][10];
    int main() {
        int n, k;
        scanf("%d%d", &n, &k);
        for(int i=1; i<=n; i++) {
            a[i][1]=1;
            a[i][0]=0;
        }
        for(int i=2; i<=k; i++) {
            a[1][i]=0;
            a[0][i]=0;
        }
        for(int i=2; i<=n; i++)
            for(int j=2; j<=k; j++)
                if(j>i) a[i][j]=0;
                else a[i][j]=a[i-1][j-1]+a[i-j][j];
        printf("%d", a[n][k]);
        return 0;
    }
    
  • 1
    @ 2016-11-20 03:46:21
    #include <iostream>
    #include <cmath>
    #include <string.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <climits>  
    #include <algorithm>  
    using namespace std;
    
    #define min(x,y) (x<y?x:y)
    
    int sum=0;
    
    void hh(int yy,int k,int u)
    {
      if(yy==0){sum++;}
      else
      {
        for(int i=min(min(yy,k),u); i>=1; i--)
          {hh(yy-i,k,i);}
      }
    }
    
    int main()
    {
      int n,k;
      cin>>n>>k;
    
      hh(n-k,k,k);
    
      cout<<sum;
    
      return 0;
    }
    
  • 0
    @ 2019-10-18 00:06:18

    暴力搜索竟然过了。。。
    代码如下:
    #include <algorithm>
    #include <iostream>
    #include <string.h>
    using namespace std;

    int ans = 0;
    int n, k;
    int vis[500];
    int save[10];

    void dfs(int tmp, int cnt)
    {
    if (cnt > k)
    {
    if (tmp == n)
    {
    ans++;
    }
    return;
    }
    for (int i = save[cnt - 1]; i < n; i++)
    {
    if (tmp + i <= n)
    {
    save[cnt] = i;
    dfs(tmp + i, cnt + 1);
    }
    else
    {
    break;
    }
    }
    }

    int main()
    {
    cin >> n >> k;
    save[0] = 1;
    dfs(0, 1);
    cout << ans<< endl;
    system("pause");
    return 0;
    }

  • 0
    @ 2017-10-18 09:00:00

    就是暴力枚举
    #include<iostream>
    #include<cstdio>
    using namespace std;

    int main()
    {
    int n,k,t=0,k1;
    scanf("%d%d",&n,&k1);
    if(k1==2){
    for(int i=1;i<=n-k1+1;i++)
    for(int j=1;j<=n-k1+1;j++)
    if(i+j==n&&i>=j){
    t++;
    j = n-k1+2;
    }
    cout<<t;return 0;
    }
    if(k1==3){
    for(int i=1;i<=n-k1+1;i++)
    for(int j=1;j<=n-k1+1;j++)
    for(int k=1;k<=n-k1+1;k++)
    if(i+j+k==n&&i>=j&&j>=k){
    t++;
    k = n-k1+2;
    }
    cout<<t;return 0;
    }
    if(k1==4){
    for(int i=1;i<=n-k1+1;i++)
    for(int j=1;j<=n-k1+1;j++)
    for(int k=1;k<=n-k1+1;k++)
    for(int l=1;l<=n-k1+1;l++)
    if(i+j+k+l==n&&i>=j&&j>=k&&k>=l)
    {
    t++;
    l = n-k1+2;
    }
    cout<<t;return 0;
    }
    if(k1==5){
    for(int i=1;i<=n-k1+1;i++)
    for(int j=i;j<=n-k1+1;j++)
    if(i+j<n)
    for(int k=j;k<=n-k1+1;k++)
    if(i+j+k<n)
    for(int l=k;l<=n-k1+1;l++)
    {
    int u = n-i-j-k-l;
    if(l<=u&&u>0)t++;
    }
    cout<<t;return 0;
    }
    if(k1==6){
    for(int i=1;i<=n-k1+1;i++)
    for(int j=i;j<=n-k1+1;j++)
    if(i+j<n)
    for(int k=j;k<=n-k1+1;k++)
    if(i+j+k<n)
    for(int l=k;l<=n-k1+1;l++)
    if(i+j+k+l<n)
    for(int u=l;u<=n-k1+1;u++)
    {
    int v=n-i-j-k-l-u;
    if(u<=v) t++;
    }
    cout<<t;return 0;
    }
    return 0;
    }

  • 0
    @ 2016-11-10 22:56:45
    #include <iostream>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int f[7][201][201], g[7][201];
    int main() {
        int n, k;
        cin >> n >> k;
        for(int i = 1; i <= n; i++)
            g[1][i] = 1;
        for(int i = 2; i <= k; i ++)
            for(int j = i; j <= n; j++) {
                for(int k = 1; k <= j / i; k++)
                    f[i][j][k] = f[i][j][k - 1] + g[i - 1][j - k] - f[i - 1][j - k][k - 1];
                g[i][j] = f[i][j][j / i];
            }
        cout << g[k][n] << endl;
        return 0;
    }
    

    愚蠢的我只想到了n^2k的算法

  • 0
    @ 2016-10-29 21:46:12

    #include<stdio.h>
    int a=1,tot=0,n,k;
    void aprt(int m,int n)
    {
    if(m>k)
    {if(n==0)tot++;return ;}
    if(n<0||n-k-1+m<0) return ;
    for(int i=a;i<=n;i++)
    {
    a=i;
    aprt(m+1,n-i);
    }
    }
    int main()
    {
    scanf("%d%d",&n,&k);
    aprt(1,n);
    printf("%d",tot);
    return 0;
    }

  • 0
    @ 2016-10-25 23:09:35
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstdio>
    #include <iomanip>
    #include <cstring>
    #include <ctime>
    using namespace std;
    
    int dg(int n,int k,int i)
    {
        if (k==1) return 1;
        int ans=0;
        for(int z=i;z<=n/k;z++)
        {
            ans+=dg(n-z,k-1,z);
        }
        return ans;
    }
    
    int main()
    {
        int a,b;
        cin>>a>>b;
        cout<<dg(a,b,1);
        return 0;
    }
    

    为毛我写了这么短......

    • @ 2016-11-16 16:09:08

      因为你短....

  • 0
    @ 2016-10-25 23:07:12

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstdio>
    #include <iomanip>
    #include <cstring>
    #include <ctime>
    using namespace std;

    int dg(int n,int k,int i)
    {
    if (k==1) return 1;
    int ans=0;
    for(int z=i;z<=n/k;z++)
    {
    ans+=dg(n-z,k-1,z);
    }
    return ans;
    }

    int main()
    {
    //clock_t go,end;
    //go=clock();

    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);

    int a,b;
    cin>>a>>b;
    cout<<dg(a,b,1);

    //fclose(stdin);
    //fclose(stdout);

    //end=clock();
    //cout<<(end-go);

    return 0;
    }

  • 0
    @ 2016-09-07 18:40:46

    #include <iostream>

    using namespace std;

    int s;

    int dfs(int n,int k,int l)
    {
    if(k==1){++s;return 0;}
    int i;
    for(i=l;i<=n;++i)
    {
    if((float)(n-i)/(k-1)<i)return 0;
    dfs(n-i,k-1,i);
    }
    }

    int main()
    {
    int n,k;
    cin>>n>>k;
    dfs(n,k,1);
    cout<<s;
    // system("pause");
    return 0;
    }

  • 0
    @ 2016-07-14 19:48:23

    脑子里出现的第一个想法。应该算简单吧?
    #include<iostream>
    using namespace std;
    int qqq(int n,int k)
    {
    if(n < k)
    return 0;
    if((n == k)||(k==1))
    return 1;
    if(n > k)
    return qqq(n-1,k-1) + qqq(n-k,k);
    }
    int main()
    {
    int n,k;
    cin >> n >> k;
    cout << qqq(n,k);
    return 0;
    }

  • 0
    @ 2016-06-14 20:14:47

    #include<cstdio>
    int main()
    {
    scanf("%d%d",&m,&n);m-=n;
    for(int i=1;i<=m;++i) f[1][i]=1;
    for(int i=2;i<=n;++i)
    {
    f[i][0]=1;
    for(int j=1;j<i;++j) f[i][j]=f[i-1][j];
    for(int j=i;j<=m;++j) f[i][j]=f[i-1][j]+f[i][j-i];
    }
    printf("%d\n",f[n][m]);
    }

  • 0
    @ 2016-05-24 17:35:05

    这道题需要动归?
    ```c++
    #include<iostream>
    #include<cstdio>
    using namespace std;

    int n;
    int k;

    int dfs (int a, int b, int c) {
    if (b == 1) return 1;
    int res = 0;
    int m = a / b;
    for (int i = c; i <= m; i++) {
    res += dfs (a - i, b - 1, i);
    }
    return res;
    }

    int main ()
    {
    //freopen ("in.txt", "r", stdin);
    cin >> n >> k;
    cout << dfs (n, k, 1);
    return 0;
    }
    ```

    • @ 2016-08-04 14:59:00

      mdzz动归不会做

  • 0
    @ 2015-12-16 14:21:37

    #include <stdio.h>
    #include <string.h>

    int f(int n,int k)//n个数分成k份
    {
    if(k>n)
    return 0;
    if(k==1)
    return 1;
    if(k==n)
    return 1;
    //最小的那个数是不是1
    return f(n-k,k)/*不是,则每个数都比1大,可以全部-1*/+f(n-1,k-1)/*是,则可以转化为去掉那个1后分成k-1份*/;
    }

    int main()
    {
    int n,k;
    scanf("%d%d",&n,&k);
    printf("%d\n",f(n,k));
    }

  • 0
    @ 2015-11-06 20:10:45

    #水一发超短
    #include<cstdio>
    using namespace std;
    int c[300][10];
    int main() {
    int n, k; scanf("%d%d", &n, &k); for(int i=1; i<=n; i++){ c[i][1] = 1; for(int j=2; j<=i&&j<=k; j++) c[i][j] = c[i-1][j-1] + c[i-j][j]; } printf("%d", c[n][k]);
    return 0;
    }

信息

ID
1117
难度
3
分类
动态规划 点击显示
标签
递交数
6203
已通过
3142
通过率
51%
被复制
13
上传者