题解

244 条题解

  • 8
    @ 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;
    }
    
  • 7
    @ 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
    @ 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
    @ 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;
    }

  • 1
    @ 2015-06-30 11:13:35

    DP我不会,我的做法是这样的,把此题假想成:n块蛋糕放入k个篮子。因为不能有空,一开始k个篮子都有1块蛋糕,然后每一次可以将j~n篮子内都加1块蛋糕(1<=j<=n),如果这样做,下一次加的时候只能从j或比j大的篮子里开始加(防止重复放法),刚好放完n块蛋糕则为一种方法。

    剪枝:j的循环从大到小,某一次放蛋糕后若蛋糕总数>n或无法放蛋糕,则更小的j不用考虑(因为j越小要放的越多)

    #include<stdio.h>
    int n,k,ans=0;

    int search(int count,int start)
    {
    int i;

    if(count==n) {ans++;return 1;}

    else if(count>n) return 0;

    for(i=k;i>=start;i--)
    if(search(count+k-i+1,i)==0) break;

    if(i==k) return 0;
    else return 1;
    }

    int main( )
    {
    scanf("%d %d",&n,&k);

    if(search(k,1));

    printf("%d",ans);
    }

  • 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
    @ 2019-07-30 22:58:12

    动态规划,以所分的数含不含1来递推,还是我的代码短^_^
    #include<iostream>
    #include<algorithm>
    using namespace std;

    int num[202][8];
    int getNum(int n,int k){
    if(n<k) return 0;
    if(k==1 || n==k) return 1;
    return num[n][k]=getNum(n-k,k)+getNum(n-1,k-1);
    }

    int main(){
    int n,k;
    cin>>n>>k;
    cout<<getNum(n,k)<<endl;
    return 0;
    }

  • 0
    @ 2018-08-07 09:02:35
    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    const int N=10000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7654321;
    const double PI=3.1415926;
    const double eps=1e-8;
    
    int n,k;
    ll f[201][10];
    int main() {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        cin>>n>>k;
        f[0][0]=1;
        FOR(i,n) FOR(j,k) {
            REP(l,0,j) if (i-l-(j-l)>=0) f[i][j]+=f[i-l-(j-l)][j-l];
            //cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
        }
        cout<<f[n][k]<<endl;
        
        return 0;
    }
    
  • 0
    @ 2018-03-29 19:47:49

    原来是s[k][n]的dp就够了啊,我用的是s[k][m][n],多了一个最大值。状态是前K个数,最大值为m,和为n的组合数量。不过这个规模O(k*n^2)也不太需要去考虑时间了。

  • 0
    @ 2017-08-01 15:18:55
    #include<cstdio>
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    int n,k;
    int f(int a,int b,int c)
    {
        int g=0,i;
        if(b==1)
        g=1;
        else
        for(i=c;i<=a/b;i++)
        g+=f(a-i,b-1,i);
        return g;
    }
    int main()
    {
        cin>>n>>k;
        cout<<f(n,k,1);
        return 0;
    }
    
  • 0
    @ 2017-06-25 16:45:40
    #include<iostream>
    using namespace std;
    long long n,k,ans;
    void dfs(int t,int s,int b)
    {
        int i;
        //if(n==200&&k==6)
        //ans=4132096;
        else
        {
        if(s==n&&t==k){
            ans++;
            return;
        }
        if(s==n||t==k) return;
        for(i=b;i<=n-s;i++)
        if(s+i<=n) dfs(t+1,s+i,i);
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin>>n>>k;
        dfs(0,0,1);
        cout<<ans;
        return 0;
    }
    
  • 0
    @ 2017-04-28 16:54:04

    #include<stdio.h>
    #include<string.h>
    #define fijk f[n][k][x]
    int f[300][10][300];
    int dijk(int n,int k,int x){
    if(k==1) return fijk=1;
    else if(~fijk) return fijk; fijk=0;
    for(int i=x;i<=n/k;++i) fijk+=dijk(n-i,k-1,i);
    return fijk;
    }
    int main(){
    int n,k; scanf("%d%d",&n,&k);
    memset(f,-1,sizeof f);
    printf("%d\n",dijk(n,k,1));
    }

  • 0
    @ 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
    @ 2016-11-17 20:06:04

    #include<iostream>
    using namespace std;
    int fenjie(int n,int k,int a){
    if(k==1){
    return 1;
    }
    int m=0;
    int q=n/k;
    for(int i=a;i<=q;i++){
    m+=fenjie(n-i,k-1,i);
    }
    return m;
    }
    int main(){
    int n,k;
    cin>>n>>k;
    cout<<fenjie(n,k,1);
    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

      因为你短....

信息

ID
1117
难度
3
分类
动态规划 点击显示
标签
递交数
6032
已通过
3056
通过率
51%
上传者