题目链接
https://codeforces.com/gym/102428/problem/F
题意
给定 $m$ 个砖块，要把这些砖块放入 $n$ 列中，其中每列最少有一个砖块，且排布上不能出现凹陷之处(即最多只有一个单峰)
题解
场上用了个傻逼方法推了贼久。。
如果没有单峰显然是个分拆数，有单峰的话需要修改一下 DP 方程
考虑两种操作，在两侧就加 $1$ 和整体加一，那么很容易得到转移
可是对 $1$ $2$ $1$ 这种数据，会计重，因此需要减去同时在两侧加上 $1$ 的情况，最后
如果一开始是空的，加 $1$ 的方案就只有一种，因此需要特判 $d[i][i]=1$
另一种解法：
网友们似乎都是从低向上叠的，考虑 $d[i][j]$ 为 剩下 $i$ 个砖块，底层是 $j$ 的方案数
那么，可以直接往上叠，也可以去掉最左边的底或者最右边的底，同样会出现 $1$ $2$ $1$ 这中情况，需要去重，有
先放砖块后转移就可以了
代码
解法一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<complex>
#include<cstdlib>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1<<(x))
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid (x+y>>1)
#define NM 5005
#define nm 505
using namespace std;
const double pi=acos(-1);
const ll inf=1e9+7;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,m;
ll d[NM][NM];
int main(){
n=read();m=read();
d[0][0]=1;
inc(i,1,n){
d[i][i]=1;
inc(j,i+1,m)if(i>1&&j>1)d[i][j]=(d[i][j-i]+2*d[i-1][j-1]-d[i-2][j-2]+inf)%inf;
else d[i][j]=(d[i][j-i]+2*d[i-1][j-1])%inf;
}
return 0*printf("%lld\n",d[n][m]);
}
|
解法二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<complex>
#include<cstdlib>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1<<(x))
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid (x+y>>1)
#define NM 5005
#define nm 505
using namespace std;
const double pi=acos(-1);
const ll inf=1e9+7;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,m;
ll d[NM][NM];
int main(){
n=read();m=read();m-=n;
inc(i,0,n)d[0][i]=1;
inc(i,1,m)inc(j,1,n)
if(j>1)
if(i>=j)d[i][j]=(d[i-j][j]+d[i][j-1]*2-d[i][j-2]+inf)%inf;
else d[i][j]=(d[i][j-1]*2-d[i][j-2]+inf)%inf;
else if(i>=j)d[i][j]=(d[i-j][j]+d[i][j-1]*2)%inf;
else d[i][j]=d[i][j-1]*2%inf;
printf("%lld\n",d[m][n]);
return 0;
}
|
