wordpress 仿站 主题,国外效果做的好的网站,欧式建筑网站,wap手机网站建站题目来源于#xff1a;洛谷 题目本质#xff1a;动态规划dp#xff0c;枚举
解题思路#xff1a;将整个洞分成两半#xff0c;一半递增#xff0c;一半递减。我们分别 DP 求值#xff0c;最后合并。状态转移方程为#xff1a;dpi,jk2∑j(j−k1)dpi−1,k1。枚举极…题目来源于洛谷 题目本质动态规划dp枚举
解题思路将整个洞分成两半一半递增一半递减。我们分别 DP 求值最后合并。状态转移方程为dpi,jk2∑j(j−k1)dpi−1,k1。枚举极大最长行区间来代替最长行。
代码如下
#includebits/stdc.h
using namespace std;
const int mod1000000007;
const int N2000,MN;
int n,m;
int dp[N1][M1];
int Sum[N1][M1],Sumk[N1][M1];
int sum[N2];
int main(){cinnm;for(int i2;im;i){dp[1][i]1;Sum[1][i](Sum[1][i-1]dp[1][i])%mod,Sumk[1][i](Sumk[1][i-1]-1ll*i*dp[1][i])%mod;}for(int i2;in;i){for(int j2;jm;j){dp[i][j](1ll*(j1)*Sum[i-1][j]Sumk[i-1][j]1)%mod;Sum[i][j](Sum[i][j-1]dp[i][j])%mod;Sumk[i][j](Sumk[i][j-1]-1ll*j*dp[i][j])%mod;}}int ans0;for(int k2;km;k){for(int jn;j;j--){sum[j](1ll*sum[j1]dp[n-j1][k]-dp[n-j][k])%mod;}for(int i1;in;i){(ans1ll*(m-k1)*(dp[i][k]-dp[i-1][k])%mod*sum[i]%mod)%mod;}}cout(ansmod)%mod;return 0;
}
