首页 > 其他 > 详细

【经典】dp+数学+预处理—— F 2019-2020 ACM-ICPC Latin American Regional Programming Contest

时间:2020-04-09 00:01:02      阅读:133      评论:0      收藏:0      [点我收藏+]

这题的状态设计,预处理方式实在是太经典了!

dp[i][j]表示用了i个格子,最上面一层有j个的方案数

技术分享图片

 

这个东西是可以拆开后预处理的,如果比较抽象可以画个方格图看看

#include<bits/stdc++.h>
#define ll  long long
#define ull unsigned long long
using namespace std;
const int N=5e3+5,M=1e9+7;
const ull base=13331;
const double Pi=acos(-1.0);
const int inf=0x3f3f3f3f;
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}
    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}
    return x*f;
}
int dp[N][N],h1[N][N],h2[N][N];
int main(){
    ios::sync_with_stdio(false);
    int s,b;cin>>s>>b;dp[s][s]=1;
    for(int i=s+1;i<=b;i++){
        for(int j=s;j>=1;j--)
            h1[i-1][j]=(h1[i-1][j+1]+dp[i-1][j])%M,
            h2[i-1][j]=(h2[i-1][j+1]+(ll)dp[i-1][j]%M*j%M)%M;
        for(int j=1;j<=min(s,i);j++)
            dp[i][j]=((dp[i][j]+h2[i-j][j])%M-(ll)h1[i-j][j]*(j-1)%M+M)%M;
    }
    int ans=0;
    for(int i=1;i<=s;i++)ans=(ans+dp[b][i])%M;
    cout<<ans<<endl;
}

 

【经典】dp+数学+预处理—— F 2019-2020 ACM-ICPC Latin American Regional Programming Contest

原文:https://www.cnblogs.com/zsben991126/p/12663829.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!