1 条题解
-
0钟明轩 (zhongmingxuan) LV 8 @ 2024-10-19 14:56:36
考虑
表示前 个,最后一个在 的方案数
转移就很简单了:遍历上一个,判断距离是否合法,合法转移
代码如下:
#include <iostream> #include <cmath> using namespace std; typedef long long ll; const ll mod=1e9+7; ll n,m,t; ll f[1005][30][30]; ll a[1005]; int main(){ freopen("lock.in","r",stdin); freopen("lock.out","w",stdout); cin>>n>>m>>t; for(ll i=1;i<t;i++){ cin>>a[i]; } for(ll i=1;i<=n;i++){ for(ll j=1;j<=m;j++){ f[0][i][j]=1; } } for(ll i=1;i<=t;i++){ for(ll x=1;x<=n;x++){ for(ll y=1;y<=m;y++){ for(ll lx=1;lx<=n;lx++){ for(ll ly=1;ly<=m;ly++){ if(abs(x-lx)+abs(y-ly)<=a[i-1]){ // cout<<i<<":"<<x<<" "<<y<<" "<<lx<<" "<<ly<<" "<<f[i-1][lx][ly]<<endl; f[i][x][y]=(f[i][x][y]+f[i-1][lx][ly])%mod; } } } } } } ll ans=0; // for(ll i=1;i<=t;i++){ // for(ll x=1;x<=n;x++){ // for(ll y=1;y<=m;y++){ // cout<<f[i][x][y]<<" "; // } // cout<<endl; // } // cout<<endl; // } for(ll i=1;i<=n;i++){ for(ll j=1;j<=m;j++){ ans+=f[t][i][j]; ans%=mod; } } cout<<ans<<endl; return 0; }
- 1
信息
- ID
- 2868
- 时间
- 3000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 107
- 已通过
- 13
- 上传者