题解 - Vijos

5

账号已注销 LV 7 @ 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

我是xxx LV 8 @ 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

神圣之月 LV 9 @ 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

Jong-oo LV 8 @ 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

啡咖啡咖啡咖啡咖 LV 8 @ 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

cdqzgxxqdql LV 10 @ 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

3037989264 LV 8 @ 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

BeNoble LV 8 @ 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

CarryH_Y_H LV 8 @ 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

JerryZheng LV 8 @ 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.
\\

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

同志你nuclear拼错了

0

JerryZheng LV 8 @ 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

dddttdVIJ LV 8 @ 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

SHENZHEBEI LV 10 @ 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

nzhtl1477 LV 10 @ 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

a292695903 LV 10 @ 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

2000F11Y10M LV 8 @ 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;
}

JerryZheng @ 2016-07-17 16:44:17

不带这样的

0

Curt_Xu LV 8 @ 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

bigbun LV 7 @ 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

niyinchen LV 9 @ 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.

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

为什么大家没用这种奇葩找规律法
niyinchen @ 2014-03-21 19:56:59

B.C. 我的知音
niyinchen @ 2014-03-21 19:58:20

容易发现：
f[n]:=f[n-1]+f[n-2]+...+f[n-m]
niyinchen @ 2014-03-21 19:58:35

初值p[0]:=1;p[1]:=2;p[2]:=4;p[3]:=8;p[4]:=16;p[5]:=32;
GoodOIer @ 2015-08-26 23:54:10

强！！！
q234rty @ 2016-01-15 20:48:11

强

0

DoraG.HS LV 6 @ 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;

｝

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

讲的很清楚，多谢！

题解

115 条题解

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

end.

核电站问题

信息

状态

开发

支持

题解

115 条题解

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

end.

核电站问题

信息

状态

开发

支持

还没有账户？

登录