/ Vijos / 题库 / 摆花 /

题解

31 条题解

  • 2
    @ 2019-08-07 14:51:16

    一维数组降低空间复杂度。

    #include <iostream>
    
    using namespace std;
    
    int n,m;
    int dp[100000]={0};
    
    int main()
    {
        cin>>n>>m;
        int i,j,a;
        dp[0]=1;
        while(n>0)
        {
            n--;
            cin>>a;
            for(i=m;i>0;i--)
            {
                for(j=1;j<=a;j++)
                {
                    if(i-j>=0)
                    {
                        dp[i]+=dp[i-j];
                    }
                }
                dp[i]=dp[i]%1000007;
            }
        }
        cout<<dp[m]<<endl;
        return 0;
    }
    
  • 1
    @ 2021-08-30 06:48:56
    #include<bits/stdc++.h>
    using namespace std;
    
    const int maxn=105, mod=1000007;
    int n,m,a[maxn],f[2][maxn],t;
    int main()
    {
        cin>>n>>m;
        for(int i=1; i<=n; i++)
            cin>>a[i];
        f[0][0] = 1;
        for(int i=1; i<=n; i++){
            t = 1-t;
            for(int j=0; j<=m; j++){
                f[t][j] = 0;
                for(int k=0; k<=min(j, a[i]); k++)
                  f[t][j] = (f[t][j] + f[1-t][j-k])%mod;
            }
        }
        cout<<f[t][m];
        return 0;
    }
    
  • 1
    @ 2018-08-08 19:08:31

    兄弟们,这次是德邦来了!
    program baihua;
    var
    f:array[0..1000,0..1000] of longint;
    a:array[1..1000] of longint;
    m,n,k,i,j,l:longint;
    begin
    read(n,m);
    for i:=1 to n do read(a[i]);
    for i:=0 to n do f[i,0]:=1;
    for i:=1 to n do
    for j:=1 to m do
    begin
    if j<a[i] then l:=j else l:=a[i];
    for k:=0 to l do
    f[i,j]:=(f[i,j]+f[i-1,j-k]) mod 1000007;
    end;
    write(f[n,m]);
    end.

  • 1
    @ 2016-09-30 13:36:44

    题解:
    c++
    #include<cstdio>
    #include<cstdlib>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<string>
    #include<iomanip>
    using namespace std;
    int a[101];
    int f[101][101];
    int main(int argc, char *argv[])
    {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    memset(f,0,sizeof(f));
    for(int i=0;i<=a[1];i++) f[1][i]=1;
    for(int i=2;i<=n;i++)
    for(int j=0;j<=m;j++)
    for(int k=0;k<=a[i];k++)
    if(j>=k)
    f[i][j]=(f[i][j]+f[i-1][j-k])%1000007;
    cout<<f[n][m];
    }

  • 0
    @ 2021-02-25 12:28:59

    //多重背包

    #include<bits/stdc++.h>
    using namespace std;
    int a[102];
    int f[10002];
    int main()
    {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    cin>>a[i];
    }
    f[0]=1;
    for(int i=1;i<=n;i++)
    {
    for(int j=m;j>=1;j--)
    {
    for(int k=1;k<=a[i];k++)
    {
    if(j-k<0)break;
    f[j]=(f[j]+f[j-k])%1000007;
    }
    }
    }
    cout<<f[m];
    }

  • 0
    @ 2016-08-16 11:16:31
    #include <bits/stdc++.h>
    using namespace std;
    int a[105],dp[105], n, m;
    int main(){
        scanf("%d %d", &n, &m);
        for(int i=1; i<=n; i++)
            scanf("%d", &a[i]);
        memset(dp,0,sizeof(dp));
        dp[0] = 1;
        for(int i=1; i<=n; i++)
            for(int j=m; j>=0; j--)
                for(int k=1; k<=min(a[i],j); k++)
                    dp[j] = (dp[j]+dp[j-k])%1000007;
        printf("%d", dp[m]%1000007);
    }
    

    DFS有毒,会完美TLE

  • 0
    @ 2015-12-08 14:31:11

    一开始想复杂了。其实就像个变形的背包问题。只需一个一维数组f,f[i]表示放i盆花的方案数。之所以这样做是因为题目规定要按编号次序摆放,也就是说依次递推即可。上代码:

    #include <stdio.h>
    int limit[200];
    int f[200];
    int main(){
    int n, m, i, j, k;
    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++)
    scanf("%d", &limit[i]);
    for(i=0; i<=m; i++)
    f[i] = 0;
    f[0] = 1;
    for(i=1; i<=n; i++){ //枚举种类
    for(j=m; j>=0; j--){ //枚举总共摆了多少
    for(k=1; k<=limit[i] && j>=k; k++) //枚举这种花摆几盆
    f[j] = (f[j]+f[j-k])%1000007;
    }
    }
    printf("%d\n", f[m]%1000007);
    return 0;
    }

  • 0
    @ 2015-10-31 10:36:52

    #include<iostream>
    using namespace std;
    const int MAXN = 100 + 10;
    const int mod = 1000007;

    int f[MAXN][MAXN], a[MAXN];

    int main()
    {
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    cin>>a[i];
    for(int i=0; i<=a[1]; i++)
    f[1][i] = 1;
    for(int i=2; i<=n; i++)
    for(int j=0; j<=m; j++)
    for(int u=0; u<=a[i]; u++)
    if(j-u >= 0)

    f[i][j] = (f[i][j] + f[i-1][j-u])%mod;
    cout<<f[n][m]<<endl;
    return 0;
    }

  • 0
    @ 2014-10-29 10:52:05

    #include<stdio.h>
    #include<algorithm>
    using namespace std;
    long long a[105],l[105],b[205][205],n,m,max1,ans;
    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    int jj=0,jm=m;

    b[0][0]=1;
    for(int i=0;i<=m;i++)
    for(int j=0;j<=n;j++)
    for(int k=j+1;k<=m;k++)
    for(int g=1;g<=a[k]&&g+i<=m;g++)
    b[i+g][k]=(b[i+g][k]+b[i][j])%1000007;
    for(int i=1;i<=n;i++)
    ans=(ans+b[m][i])%1000007;
    printf("%d",ans);
    }

  • 0
    @ 2014-10-13 16:44:38

    简单dp

    P1792摆花
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1792 摆花
    递交时间 2014-10-13 16:43:35
    代码语言 C++
    评测机 上海红茶馆
    消耗时间 60 ms
    消耗内存 640 KiB
    评测时间 2014-10-13 16:43:36

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 632 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 640 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 640 KiB, score = 10

    测试数据 #3: Accepted, time = 15 ms, mem = 636 KiB, score = 10

    测试数据 #4: Accepted, time = 0 ms, mem = 640 KiB, score = 10

    测试数据 #5: Accepted, time = 0 ms, mem = 632 KiB, score = 10

    测试数据 #6: Accepted, time = 0 ms, mem = 636 KiB, score = 10

    测试数据 #7: Accepted, time = 15 ms, mem = 640 KiB, score = 10

    测试数据 #8: Accepted, time = 15 ms, mem = 636 KiB, score = 10

    测试数据 #9: Accepted, time = 15 ms, mem = 636 KiB, score = 10

    Accepted, time = 60 ms, mem = 640 KiB, score = 100

    代码

    #include <iostream>
    #include <cmath>
    #include <stdio.h>
    #include <algorithm>

    using namespace std;

    int n , m;
    int i;
    int a[100 + 2];
    long long f[100 + 2][100 + 2];
    const int modd = 1000007;

    int dp( int i , int j )
    {
    if( i == n )
    return 0;
    if( j == m )
    return 0;
    if( f[i][j] != 0 )
    return f[i][j];
    int l;
    long long ans = 0;
    for( l = 0 ; l <= a[i] ; l++ )
    if( j + l < m )
    ans = ( ans + dp( i + 1 , j + l ) ) % modd;
    else if( j + l == m )
    ans++;
    f[i][j] = ans;
    return ans;
    }

    int main()
    {
    while( scanf( "%d %d" , &n , &m ) != EOF )
    {
    for( i = 0 ; i < n ; i++ )
    scanf( "%d" , &a[i] );
    cout << dp( 0 , 0 ) << endl;
    }
    return 0;
    }

    • @ 2015-04-08 21:27:35

      这是记忆化搜索。。。不是dp

  • 0
    @ 2014-07-20 08:34:23

    测试数据 #0: Accepted, time = 15 ms, mem = 784 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 784 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 780 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 780 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 780 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 780 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 780 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 780 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 780 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 776 KiB, score = 10

  • 0
    @ 2014-05-22 20:15:55

    c++中答案数组要用long,不能用int,不然拿数据手测能过,交就只有70分了

  • 0
    @ 2013-11-08 15:42:46

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 820 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 820 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 828 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 824 KiB, score = 10

    Accepted, time = 15 ms, mem = 828 KiB, score = 100

    Code:
    var
    i,j,k,n,m:longint;
    a,f:array[0..100]of longint;
    begin
    readln(n,m);
    for i:=1 to n do
    read(a[i]);
    f[0]:=1;
    for i:=1 to n do
    for j:=m downto 1 do
    for k:=1 to a[i] do
    if j>=k then
    f[j]:=(f[j]+f[j-k])mod 1000007;
    write(f[m]);
    end.

  • 0
    @ 2013-10-29 22:33:30

    var a:array[0..100,0..100] of longint;
    b:array[0..100] of longint;
    i,j,k,l,q,w,e,n,m,s:longint;
    function max(x,y:longint):longint;
    begin
    if x>y then exit(x) else exit(y);
    end;
    begin
    readln(n,m); fillchar(a,sizeof(a),0);
    // for i:=1 to n do b[i]:=100;
    for i:=1 to n do read(b[i]);
    for i:=0 to b[1] do a[1,i]:=1;
    for i:=2 to n do
    begin
    for j:=0 to m do
    begin
    for k:=max(0,j-b[i]) to j do a[i,j]:=a[i-1,k]+a[i,j];a[i,j]:=a[i,j] mod 1000007;end;
    end;
    writeln(a[n,m]);
    end.

  • 0
    @ 2013-10-25 15:16:59

    学习了。这题的去模要很注意啊。不可以到最后再取!!

  • 0
    @ 2013-10-24 20:08:46

    测试数据 #0: Accepted, time = 0 ms, mem = 864 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 868 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 860 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 864 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 864 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 864 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 860 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 860 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 864 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 860 KiB, score = 10
    Accepted, time = 0 ms, mem = 868 KiB, score = 100
    **********************************晒程序***************************************
    Program p1792;
    var n,m,i,j,k:longint;
    a:array[1..100] of longint;
    f:array[0..100,0..100] of longint;
    Begin
    readln(n,m);
    for i:=1 to n do
    read(a[i]);
    fillchar(f,sizeof(f),0);
    f[0,0]:=1;
    for i:=1 to n do
    for j:=0 to m do
    for k:=0 to a[i] do
    if j-k>=0 then
    f:=(f+f) mod 1000007
    else break;
    writeln(f[n,m]);
    end.

  • 0
    @ 2013-10-09 21:38:21

    其实这就是个普通的背包,一位背包秒之,注意取模= =,当初就是没去WA了
    var
    n,m,i,j,x,k:longint;
    f:array[-100..200]of longint;
    begin
    readln(n,m);
    fillchar(f,sizeof(f),0);
    f[0]:=1;
    for i:=1 to n do
    begin
    read(x);
    for j:=m-1 downto 0 do
    if(f[j]>0)then
    for k:=1 to x do
    begin
    inc(f[j+k],f[j]);
    f[j+k]:=f[j+k] mod 1000007;
    end;
    end;
    writeln(f[m]);
    end.

  • 0
    @ 2013-08-19 17:39:25

    哦,老天,想着longint够大,所以只有在最后才mod1000007,搞到错了n次,小心,每次做和后都要mod...

信息

ID
1792
难度
5
分类
动态规划 点击显示
标签
递交数
2541
已通过
795
通过率
31%
被复制
10
上传者