题解

115 条题解

  • 5
    @ 2017-10-14 10:55:46

    二维!
    dp[i][j]表示第i个坑已经连续放了j个有多少种可能。
    如果i>0,dp[i][j]=dp[i-1][j-1];否则,就是i上一状态所有的和。

    #include<cstdio>
    long long  dp[55][6];
    long long  s=0;
    int main()
    {
        int n,m,i,j,k;
        scanf("%d%d",&n,&m);
        dp[1][0]=1; dp[1][1]=1;
        for (i=2;i<=n;i++)
            for (j=0;j<m;j++)
                if (j) dp[i][j]=dp[i-1][j-1];
                else
                    for (k=0;k<m;k++) dp[i][j]+=dp[i-1][k];
        for (i=0;i<m;i++) s+=dp[n][i];
        printf("%lld",s);
        return 0;
    }
    

    一维!

    #include<cstdio>
    long long  dp[55];
    int main()
    {
        int n,m,i;
        scanf("%d%d",&n,&m);
        dp[0]=1;
        for (i=1;i<=n;i++)
            if (i==m) dp[i]=dp[i-1]*2-1;     //减掉都放。 
            else
            if (i<m) dp[i]=dp[i-1]*2;        //随便放不会炸。 
            else dp[i]=dp[i-1]*2-dp[i-m-1];
            /*后m个固定放时前面的有dp[i-m]种放法,这些放法中都不可取。
            但是这些放法中包含了第(i-m)放与不放两种可能,第(i-m)放的可能在(i-1)中就已排除,所以只需再排除不放的情况,即dp[i-m-1]。*/ 
        printf("%lld",dp[n]);
        return 0;
    }
    
  • 1
    @ 2016-11-01 19:22:26

    没加long long就WA了4个点。。。

    #include<cstdio>
    #include<iostream>
    using namespace std;
    int n,m,i,j;
    long long s;
    long long f[51][5];
    main()
    {
    scanf("%d%d",&n,&m);
    f[0][0]=1;
    for(i=1;i<=n;i++)
    {
    s=0;
    for(j=0;j<m;j++) s+=f[i-1][j];
    f[i][0]=s;
    for(j=1;j<=min(m-1,i);j++)
    f[i][j]=f[i-1][j-1];
    }
    s=0;
    for(i=0;i<m;i++) s+=f[n][i];
    printf("%lld",s);
    }

  • 1
    @ 2013-04-17 19:14:53

    var
    n,m,i,j,k,l:longint;
    f:array[-3..60]of int64;
    begin
    readln(n,m);
    f[-1]:=1;
    f[0]:=1;
    for i:=1 to n do
    if i<m then f[i]:=f[i-1]*2
    else f[i]:=f[i-1]*2-f[i-m-1];
    writeln(f[n]);
    end.
    程序在上
    f[i]表示 的是从1 至 n 的最大方案数
    易知 当i<m 时 f[i]=f[i-1]*2 (第i个只有两种方法)
    当 i>=m 时

    设 前i个为 Q1 Q2 Q3 Q4...... Qi-m-1 Qi-m ....Qi
    因为 已知 f[i-1] 则 Qi-m...Qi-1 中不存在 全都有的情况
    所以只需考虑 从 Qi-m+1.....Qi 都有的情况 此时 Qi-m 不可放
    所以 从 Qi-m+1.....Qi 都有的情况 总数就是 f[i-m-1]
    所以 当 i>=m 时 f[i]=f[i-1]*2-f[i-m-1]
    程序核心
    for i:=1 to n do
    if i<m then f[i]:=f[i-1]*2
    else f[i]:=f[i-1]*2-f[i-m-1];

    不过不要忘记考虑初始化
    f[0]=1;f[1]=1;
    最后 一点 用int64

  • 0
    @ 2020-11-09 10:37:18
    // dp[i][j] 表示第i个坑已经放置j个连续时的方案数
    // 每个坑有放与不放两个选择
    // 放: dp[i][j] = dp[i - 1][j - 1]
    // 不放(即把当前留为空): dp[i][0] += dp[i - 1][k] (0 <= k < m)
    
    #include <algorithm>
    #include <iostream>
    #include <string>
    using namespace std;
    typedef long long ll;
    const int maxn = 52;
    int N, M;
    ll ans;
    ll dp[maxn][6];  
    
    int main() {
        cin >> N >> M;
        dp[1][1] = 1, dp[1][0] = 1;
    
        for (int i = 2; i <= N; i++)
            for (int j = 0; j < M; j++) {
                if (j)
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    for (int k = 0; k < M; k++) dp[i][j] += dp[i - 1][k];
            }
        for (int j = 0; j < M; j++) ans += dp[N][j];
        cout << ans << endl;
    
        return 0;
    }
    
    
    
  • 0
    @ 2018-08-08 11:56:58
    /*pwq*/
    #include<cstdio> 
    int n,m;
    long long f[100]; 
    int main()
    {
        scanf("%d%d",&n,&m);
        f[0]=1;
        for(int i=1;i<=n;i++)
        {
            if(i<m)
                f[i]=2*f[i-1];
            else if(i==m)
                f[i]=2*f[i-1]-1;
            else
                f[i]=2*f[i-1]-f[i-m-1];
        }
        printf("%lld",f[n]);
        return 0;
    }
    
    
  • 0
    @ 2017-08-22 17:21:59
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    long long dp[55][2][10];//必须longlong 
    int main()
    {
        int n,m;cin>>n>>m;
        if(m==1)
        {
            printf("1");return 0;
        }
        dp[1][0][0]=1;dp[1][1][0]=1;
        for(int i=1;i<=n;i++)
        for(int j=0;j<=min(i,m-1);j++)
        {
            if(j>0)
                dp[i+1][0][j]+=dp[i][1][j-1];
            dp[i+1][0][0]+=dp[i][0][j];
            dp[i+1][1][0]+=dp[i][0][j];
            if(j>0&&j!=m-1)
                dp[i+1][1][j]+=dp[i][1][j-1];
        }
        long long ans=0;
        for(int i=0;i<m;i++)
            ans+=dp[n][0][i]+dp[n][1][i];
        cout<<ans;return 0;
    }
    
  • 0
    @ 2017-02-08 08:45:13

    大神都用的o(n)的做法,然而蒟蒻只会o(mn)的做法
    %%%%%
    c++
    int n,m;
    long long dp[51][6];
    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m-1;i++)dp[n][i]=2;
    dp[n][m]=1;
    for(int i=n-1;i>=1;i--)
    for(int j=1;j<=m;j++)
    {
    if(j<m)dp[i][j]+=dp[i+1][j+1];
    dp[i][j]+=dp[i+1][1];
    }
    printf("%lld",dp[1][1]);
    return 0;
    }

  • 0
    @ 2016-11-05 19:08:20

    玄学做法
    c++
    #include<cstdio>
    long long f[51]={1};int i,n,m;
    int main()
    {
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    if(i<m) f[i]=2*f[i-1];
    else if(i==m) f[i]=2*f[i-1]-1;
    else f[i]=2*f[i-1]-f[i-m-1];
    printf("%lld",f[n]);
    return 0;
    }

  • 0
    @ 2016-10-15 13:47:55

    记忆化搜素可过

    sf[i,j]表示在第i个坑1中前面已经连续放了J个

    var nn,m:longint;
    b:array[-1 .. 50] of boolean;
    sf:array[1 .. 200,1 .. 6] of int64;
    function f(n:longint):int64;
    var i:longint;
    bol:boolean;
    begin
    i := n - 1; f := 0;
    while (b[i] = true) and (i >= 1) do dec(i); inc(i);
    if sf[n,n-i+1] <> 0 then f := sf[n,n-i+1]
    else
    begin
    if (n - i + 1 < m ) then bol := true else bol := false;
    if n = nn then
    if bol then f := 2 else f := 1;
    if n <> nn then
    begin
    if bol then
    begin
    b[n] := true;
    f := f + f(n+1);
    end;
    b[n] := false;
    f := f + f(n+1);
    end;
    sf[n,n-i+1] := f;
    end;
    end;
    begin
    fillchar(b,sizeof(b),false);
    fillchar(sf,sizeof(sf),0);
    read(nn,m);
    write(f(1));

    end.

    顺便问下竞赛时不是不能用INT64吗= =

  • 0
    @ 2016-07-17 16:43:41

    不好意思楼下发错了
    评测状态 Accepted
    题目 P1232 核电站问题
    递交时间 2016-07-17 16:36:31
    代码语言 Pascal
    评测机 ShadowShore
    消耗时间 0 ms
    消耗内存 804 KiB
    评测时间 2016-07-17 16:36:32

    评测结果

    编译成功

    Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
    Copyright (c) 1993-2015 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    Linking foo.exe
    20 lines compiled, 0.0 sec, 27856 bytes code, 1268 bytes data

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

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

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

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

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

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

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

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

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

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

    Accepted, time = 0 ms, mem = 804 KiB, score = 100
    \\pascal
    //neuclear.pas
    var
    m,n,i:longint;
    f:array[-8..63]of int64;

    begin
    // assign(input,'neuclear.in');
    // assign(output,'neuclear.out');
    // reset(input);
    // rewrite(output);
    readln(n,m);
    // readln(m);
    fillchar(f,sizeof(f),0);
    f[-1]:=1;
    f[0]:=1;
    for i:=1 to n do
    f[i]:=2*f[i-1]-f[i-1-m];
    writeln(f[n]);
    // close(input);
    // close(output);
    end.
    \\

    • @ 2016-08-21 22:59:45

      同志你nuclear拼错了

  • 0
    @ 2016-07-17 16:41:43

    评测状态 Accepted
    题目 P1232 核电站问题
    递交时间 2016-07-17 16:36:31
    代码语言 Pascal
    评测机 ShadowShore
    消耗时间 0 ms
    消耗内存 804 KiB
    评测时间 2016-07-17 16:36:32

    评测结果

    编译成功

    Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
    Copyright (c) 1993-2015 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    Linking foo.exe
    20 lines compiled, 0.0 sec, 27856 bytes code, 1268 bytes data

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

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

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

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

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

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

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

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

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

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

    Accepted, time = 0 ms, mem = 804 KiB, score = 100

    '''pascal
    //neuclear.pas
    var
    m,n,i:longint;
    f:array[-8..63]of int64;

    begin
    // assign(input,'neuclear.in');
    // assign(output,'neuclear.out');
    // reset(input);
    // rewrite(output);
    readln(n,m);
    // readln(m);
    fillchar(f,sizeof(f),0);
    f[-1]:=1;
    f[0]:=1;
    for i:=1 to n do
    f[i]:=2*f[i-1]-f[i-1-m];
    writeln(f[n]);
    // close(input);
    // close(output);
    end.

    '''

  • 0
    @ 2016-01-26 15:40:27

    #include<iostream>
    using namespace std;
    int m,n;
    long long a[51],k;
    int main()
    {
    a[0]=1;
    a[1]=2;
    a[2]=4;
    a[3]=8;
    a[4]=16;
    a[5]=32;
    cin>>n>>m;
    for (int i=m;i<=n;i++)
    {
    k=0;
    for (int j=1;j<=m;j++)k+=a[i-j];
    a[i]=k;
    }
    cout<<a[n];
    }

  • 0
    @ 2015-09-17 18:15:52

    var
    a:array[0..50,0..5] of int64;
    i,j,k,m,n:longint;
    sum:int64;
    begin
    readln(n,m);
    a[0,0]:=1;
    for i:=1 to n do
    begin
    for j:=0 to m-1 do
    a[i,0]:=a[i-1,j]+a[i,0];
    for j:=1 to m-1 do
    a[i,j]:=a[i-1,j-1];
    end;
    for i:=0 to m-1 do
    sum:=sum+a[n,i];
    writeln(sum);
    end.

  • 0
    @ 2015-09-15 00:22:18

    记录信息

    评测状态 Accepted
    题目 P1232 核电站问题
    递交时间 2015-09-15 00:22:06
    代码语言 C++
    评测机 VijosEx
    消耗时间 39 ms
    消耗内存 516 KiB
    评测时间 2015-09-15 00:22:07

    评测结果

    编译成功

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

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

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

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

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

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

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

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

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

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

    Accepted, time = 39 ms, mem = 516 KiB, score = 100

    代码

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

    using namespace std;

    long long f[50 + 2][5 + 2];

    int n , m;

    long long dp( int pos , int times )
    {
    if( f[ pos ][ times ] != -1 )
    return f[ pos ][ times ];
    if( pos == n + 1 )
    return 1;
    if( times != m - 1 )
    return f[ pos ][ times ] = dp( pos + 1 , times + 1 ) + dp( pos + 1 , 0 );
    return f[ pos ][ times ] = dp( pos + 1 , 0 );
    }

    int main()
    {
    scanf( "%d %d" , &n , &m );
    memset( f , -1 , sizeof( f ) );
    cout << dp( 1 , 0 ) << endl;
    return 0;
    }

  • 0
    @ 2015-08-21 13:35:52

    dp[i][j]:=第i个位置 连续j个核坑的方法数
    初始化dp[0][0]=1;
    状态转移

    dp[i][0]=∑dp[i-1][k] 0<=k<m
    dp[i][k]+=dp[i-k][0]

    最后∑dp[n][k] 0<=k<m 就是答案
    注意用long long

    ll dp[100][10];//dp[i][j]:=第i个位置,由此到前面一共有j个核坑的最大的数量。。。
    int main()
    {
    int n,m;
    read(n,m);
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
    for(int k=0;k<m;k++)
    dp[i][0]+=dp[i-1][k];
    for(int j=1;j<=min(i,m-1);j++)
    dp[i][j]+=dp[i-j][0];
    }
    ll ans=0;
    for(int i=0;i<m;i++)ans+=dp[n][i];
    cout<<ans<<endl;
    }

  • 0
    @ 2014-05-15 20:10:09

    搜索就可以过了。。
    #include <stdio.h>
    #include <string.h>
    #include <iostream>
    using namespace std;
    int m,n;
    long long f[51][51];
    long long dfs();
    long long dfs(int i,int j){
    long long tmp=0;
    if (i>n)
    return 1;
    if (f[i][j]!=-1)
    return f[i][j];
    if (j<m-1)
    tmp+=dfs (i+1,j+1);
    tmp+=dfs (i+1,0);
    return f[i][j]=tmp;
    }
    int main(){
    cin>>n>>m;
    memset (f,-1,sizeof (f));
    cout<<dfs (1,0);
    return 0;
    }

  • 0
    @ 2014-05-11 01:17:15

    #include<cstdio>
    #include<vector>
    using namespace std;
    int m,n;
    vector<double>v;
    inline void f(int i);
    int main()
    {
    scanf("%d %d\n",&n,&m);
    v.push_back(1);
    for(int i=1;i<=n;i++){
    f(i);
    }
    printf("%.0f\n",v.back());
    }
    inline void f(int i){
    if(i<m){
    v.push_back(v[i-1]*2);
    }
    else if(i==m){
    v.push_back(v[i-1]*2-1);
    }
    else{
    v.push_back(v[i-1]*2-v[i-m-1]);
    }
    }

  • 0
    @ 2014-03-25 12:51:51

    先找出M或以上连续的方案数,再用总方案数减去.

    #include <cstdio>
    using namespace std;
    const int MAX = 51;
    long long dp[MAX];

    long long pow_2(int n){
    return 1LL << n;
    }
    int main(int argc, char const *argv[]){
    int N, M;
    scanf("%d%d", &N, &M);
    dp[M] = 1;
    for(int i = M + 1; i <= N; ++i){
    dp[i] = 2 * dp[i - 1] + pow_2(i - M - 1) - dp[i - M - 1];
    }
    printf("%lld\n", pow_2(N) - dp[N]);
    return 0;
    }

  • 0
    @ 2014-03-21 19:55:00

    var n,i,m,j:longint;

    p:array[0..60]of int64;

    k:int64;

    begin

    readln(n,m);

    p[0]:=1;p[1]:=2;p[2]:=4;p[3]:=8;p[4]:=16;p[5]:=32;

    for i:=m to n do

    begin

    k:=0;

    for j:=1 to m do k:=k+p[i-j];

    p[i]:=k;

    end;

    writeln(p[n]);

    end.

    • @ 2014-03-21 19:55:52

      为什么大家没用这种奇葩找规律法

    • @ 2014-03-21 19:56:59

      B.C. 我的知音

    • @ 2014-03-21 19:58:20

      容易发现:
      f[n]:=f[n-1]+f[n-2]+...+f[n-m]

    • @ 2014-03-21 19:58:35

      初值p[0]:=1;p[1]:=2;p[2]:=4;p[3]:=8;p[4]:=16;p[5]:=32;

    • @ 2015-08-26 23:54:10

      强!!!

    • @ 2016-01-15 20:48:11

  • 0
    @ 2013-11-07 18:07:20

    测试数据 #0: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 536 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 532 KiB, score = 10
    Accepted, time = 0 ms, mem = 540 KiB, score = 100

    ————————————————————————————————————————————————————

    我没那些大牛厉害,愣是盯着题解好长时间才搞定,用了两种方法——自顶向下和自底向上...
    我就卡到了f[i]=f[i-1]*2-f[i-m-1]上。现在想想也没什么。首先如果没有连续限制的话,第[i]个本来是f[i-1]*2中方案,但是如果之前(m-1)全是核弹,那么第i个就不能放了,这种情况只有一种(即i后m-1里全部是核弹),但是这还要把前面的方案乘起来——毕竟从0到f[i-m-1],要达到这么一种情况有好多种方案....
    希望能帮到和我一样的菜...
    【坑】本来能AC的,结果用long int不成WA了两次,直接上double

    自底向上——————————————————————————————————————————

    cases[0]=1;//没有坑显然只有一种方案——不填
    for(j=1;j<=N;j++)
    {
    if(j < M)
    cases[j]=cases[j-1]*2;

    else if(j == M)
    cases[j]=cases[j-1]*2-1;
    else
    cases[j]=cases[j-1]*2-cases[j-M-1]*1;
    }

    自顶向下:记住初始化——————————————————————————————————————————
    double dp(int k)
    {
    double temp;
    if(ca[k] != 0)
    temp = ca[k];
    else
    {
    if(k<m)
    temp = dp(k-1)*2;
    else if(k == m)
    temp = dp(k-1)*2-1;
    else
    temp = dp(k-1)*2 - dp(k-m-1);
    }
    return ca[k] = temp;

    • @ 2016-05-09 20:35:17

      讲的很清楚,多谢!

信息

ID
1232
难度
3
分类
动态规划 点击显示
标签
(无)
递交数
2772
已通过
1346
通过率
49%
被复制
5
上传者