南山区住房和建设局网站,企业网站托管服务常用指南,网站网站开发设计,开发公司支付给业主的购房补贴题解
我们可以先简单的想一种状态#xff0c;也就是dp[i][j][x][y][t]dp[i][j][x][y][t]dp[i][j][x][y][t]#xff0c;这是最暴力的。 当t0t 0t0时#xff0c;表示小a处于(i,j)(i,j)(i,j)位置#xff0c;其中小a拥有x魔液#xff0c;uim拥有y的魔液时候的方案总数。t1t …题解
我们可以先简单的想一种状态也就是dp[i][j][x][y][t]dp[i][j][x][y][t]dp[i][j][x][y][t]这是最暴力的。 当t0t 0t0时表示小a处于(i,j)(i,j)(i,j)位置其中小a拥有x魔液uim拥有y的魔液时候的方案总数。t1t 1t1的时候反过来意义类似。 这样的话我们很容里列出转移方程这里就不给出了但是这样的话内存和时间上都会爆炸800∗800∗15∗15∗2288000000800*800*15*15*2288000000800∗800∗15∗15∗2288000000因此我们必须对状态进行压缩。 从要求出发题目中要求两者魔力相等的方案数也就是差值为000的方案数。 我们定义 dp[i][j][x][t]dp[i][j][x][t]dp[i][j][x][t]。当t 0时候表示小a位于(i,j)位置且小a的魔力与uim的魔力相差为x的方案数。 容易列出状态转移方程 dp[i][j][x][t]dp[i][j−1][p][1−t]dp[i−1][j][p][1−t]dp[i][j][x][t] dp[i][j-1][p][1-t]dp[i-1][j][p][1-t]dp[i][j][x][t]dp[i][j−1][p][1−t]dp[i−1][j][p][1−t] 其中p(mat[i][j]−tk)%kp (mat[i][j]-tk)\%kp(mat[i][j]−tk)%k 推导过程 sumtmat[i][j]−sum1−txsum_t mat[i][j] - sum_{1-t} xsumtmat[i][j]−sum1−tx psum1−t−sumtmat[i][j]−x(mat[i][j]−xk)%kp sum_{1-t}-sum_t mat[i][j] - x (mat[i][j]-xk)\%kpsum1−t−sumtmat[i][j]−x(mat[i][j]−xk)%k 额外条件要注意 由于只能从小a开始因此初始化只初始化t0t 0t0的情况 由于只能从uim结束因此答案只加dp[i][j][0][1]dp[i][j][0][1]dp[i][j][0][1] 代码
#include iostream
#include cstdio
using namespace std;
int n,m,k;
int dp[801][801][20][2];
const int mod 1e97;
int mat[801][801];
int main(){scanf(%d%d%d,n,m,k);k;for(int i 1;i n;i){for(int j 1;j m;j){scanf(%d,mat[i][j]);dp[i][j][mat[i][j]%k][0] 1;}}long long ans 0;for(int i 1;i n;i){for(int j 1;j m;j){for(int t 0;t k;t){int p (mat[i][j]-tk)%k;dp[i][j][t][0] (dp[i-1][j][p][1]dp[i][j-1][p][1])%mod;//p (mat[i][j]t)%k;dp[i][j][t][1] (dp[i-1][j][p][0]dp[i][j-1][p][0])%mod;dp[i][j][t][0] % mod;dp[i][j][t][1] % mod;//printf(i:%d,j:%d,t:%d,val:%d\n,i,j,t,dp[i][j][t][1]);}ans (ans dp[i][j][0][1])%mod;}}coutansendl;
}
