【BZOJ3939】[Usaco2015 Feb]Cow Hopscotch 动态规划+线段树
【BZOJ3939】[Usaco2015 Feb]Cow Hopscotch
Description
Just like humans enjoy playing the game of Hopscotch, Farmer John's cows have invented a variant of the game for themselves to play. Being played by clumsy animals weighing nearly a ton, Cow Hopscotch almost always ends in disaster, but this has surprisingly not deterred the cows from attempting to play nearly every afternoon.
The game is played on an R by C grid (2 <= R <= 750, 2 <= C <= 750), where each square is labeled with an integer in the range 1..K (1 <= K <= R*C). Cows start in the top-left square and move to the bottom-right square by a sequence of jumps, where a jump is valid if and only if
1) You are jumping to a square labeled with a different integer than your current square,
2) The square that you are jumping to is at least one row below the current square that you are on, and
3) The square that you are jumping to is at least one column to the right of the current square that you are on.
Please help the cows compute the number of different possible sequences of valid jumps that will take them from the top-left square to the bottom-right square.
Input
Output
Output the number of different ways one can jump from the top-left square to the bottom-right square, mod 1000000007.
Sample Input
1 1 1 1
1 3 2 1
1 2 4 1
1 1 1 1
Sample Output
题解:标号不同的方案数=总方案数 - 标号相同的方案数
总的方案数我们可以用前缀和轻松搞定,标号相同的方案数怎么搞?
(一开始想用树状数组,结果发现标号种类太多RE了)
所以我们只能采用动态开点线段树,对每种标号都开一棵线段树来维护前缀和就好了
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define mod 1000000007 using namespace std; int n,m,K,tot; int map[800][800],f[800][800],sum[800]; struct Seg { int ls,rs,cnt; }s[6001000]; void updata(int l,int r,int &x,int y,int v) { if(!x) x=++tot; if(l==r) { s[x].cnt=(s[x].cnt+v)%mod; return ; } int mid=l+r>>1; if(y<=mid) updata(l,mid,s[x].ls,y,v); else updata(mid+1,r,s[x].rs,y,v); s[x].cnt=(s[s[x].ls].cnt+s[s[x].rs].cnt)%mod; } int query(int l,int r,int x,int y) { if(!x) return 0; if(r<=y) return s[x].cnt; int mid=l+r>>1; if(y<=mid) return query(l,mid,s[x].ls,y); return (query(l,mid,s[x].ls,y)+query(mid+1,r,s[x].rs,y))%mod; } int main() { scanf("%d%d%d",&n,&m,&K); tot=K; int i,j,t; for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&map[i][j]); f[1][1]=1; for(i=1;i<m;i++) sum[i]=1; updata(1,m,map[1][1],1,1); for(i=2;i<n;i++) { for(j=2;j<m;j++) f[i][j]=(sum[j-1]-query(1,m,map[i][j],j-1)+mod)%mod; t=0; for(j=2;j<m;j++) { t=(t+f[i][j])%mod; sum[j]=(sum[j]+t)%mod; updata(1,m,map[i][j],j,f[i][j]); } } printf("%d",(sum[m-1]-query(1,m,map[n][m],m-1)+mod)%mod); return 0; }
相关文章
- 算法知识之最长公共子序列问题(动态规划)
- Java实现 LeetCode 730 统计不同回文子字符串(动态规划)
- Java实现 LeetCode 730 统计不同回文子字符串(动态规划)
- Java实现 LeetCode 600 不含连续1的非负整数(有些题为了避免使用位运算可以换成动态规划)
- Java实现 LeetCode 343 整数拆分(动态规划入门经典)
- 聊聊 RPA 方向的规划:简单有价值的事情长期坚持做
- 动态规划之最长公共子序列
- [usaco]5.3.2 Milk Measuring 动态规划
- Atitit 软件与开发的未来趋势 attilax总结 1.1. Sdx软件重构世界 软件定义未来1 1.2. 《软件和信息技术服务业发展规划(2016-2020年)》(2 1.3. Iot物联
- atitit.短信 验证码 破解 v3 p34 识别 绕过 系统方案规划----业务相关方案 手机验证码 .doc
- Atitit. Ati IDE 开发平台的第一版规划
- Atitit。sql2016标准化的规划方案 v3 q2a
- Atitit。sql2016标准化的规划方案 v3 q2a
- atitit.信息系统方案规划 p71.doc
- 【henuacm2016级暑期训练-动态规划专题 C】Little Girl and Maximum XOR
- 【 henuacm2016级暑期训练-动态规划专题 A 】Cards
- 【机组组合】基于Benders分解算法解决混合整数规划问题——机组组合问题(Matlab代码实现)
- 【优化模型】求解二次规划问题
- 410. 分割数组的最大值-前缀和加动态规划算法
- 583. 两个字符串的删除操作-动态规划
- [LeetCode] 121. 买卖股票的最佳时机 ☆(动态规划)
- 动态规划 背包问题算法模板 0-1背包 0-1带价值背包 多重背包问题
- 07-图6 旅游规划
- 动态规划——背包问题