1 条题解

  • 0
    @ 2024-10-19 14:56:36

    考虑dpdp

    fi,x,yf_{i,x,y} 表示前 ii 个,最后一个在 x,yx,y 的方案数

    转移就很简单了:遍历上一个,判断距离是否合法,合法转移

    代码如下:

    #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
    上传者