博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Black and White
阅读量:6495 次
发布时间:2019-06-24

本文共 1327 字,大约阅读时间需要 4 分钟。

Black and White

题目链接:

DP

按照常规想法会这样定义状态:dp[当前位数i][当前位是否为黑][连续棋子的个数k]为符合状态的方案数,

但是题目中a,b,n均为1e6,不论空间还是时间都不允许这样做,考虑另外的状态定义:

  dp[当前位数i][当前位是否为黑]表示符合状态的合法的方案数;

当前位数大于最大连续棋子数(a,b)时,dp[i][1]=dp[i-1][1]+dp[i-1][0]中包含了连续a个黑棋的非法状态,

而连续a个黑棋的非法状态数与dp[i-a][0]相同(第i-a位到第i位只有均为黑一种情况),将其删去即为合法状态;白棋亦然。

于是状态转移方程为:

  • 当i<a&&i<b(从下标1开始)时,
    • dp[i][1]=dp[i-1][1]+dp[i-1][0];
    • dp[i][0]=dp[i-1][1]+dp[i-1][0];
  • 当i>=a||i>=b时,
    • dp[i][1]=dp[i-1][1]+dp[i-1][0];
    • dp[i][0]=dp[i-1][1]+dp[i-1][0];
    • dp[i][1]=dp[i][1]-dp[i-a][0];
    • dp[i][0]=dp[i][0]-dp[i-b][1];

代码如下:

1 #include 
2 #include
3 #include
4 #include
5 #include
6 #define N 1000005 7 using namespace std; 8 typedef long long ll; 9 ll m=1e9+7;10 ll T,a,b,n,dp[N][2];11 int main(void){12 std::ios::sync_with_stdio(false);13 dp[0][1]=dp[0][0]=dp[1][1]=dp[1][0]=1;14 cin>>T;15 while(T--){16 cin>>a>>b>>n;17 for(int i=2;i<=n;++i){18 dp[i][1]=(dp[i-1][1]+dp[i-1][0])%m;19 dp[i][0]=(dp[i-1][1]+dp[i-1][0])%m;20 if(i>=a)dp[i][1]=(dp[i][1]-dp[i-a][0]+m)%m;21 if(i>=b)dp[i][0]=(dp[i][0]-dp[i-b][1]+m)%m;22 }23 cout<<(dp[n][0]+dp[n][1])%m<<"\n";24 }25 }

 

转载于:https://www.cnblogs.com/barrier/p/6415990.html

你可能感兴趣的文章
6年iOS开发程序员总结组件化—让你的项目一步到位
查看>>
没有学不会的C++:用户自定义的隐式类型转换
查看>>
TiKV 成功晋级 CNCF 孵化项目
查看>>
X5同层播放器应用实践
查看>>
在javascript中判断类型
查看>>
好用漂亮的Android 表格框架
查看>>
css3伪元素选择器before 和 after 的使用
查看>>
从 Flutter 的视频渲染到 App 落地经验
查看>>
Redis的KEYS命令引起宕机事件
查看>>
仿美团外卖的全栈项目(vue+node+mongodb)带支付->大三求实习
查看>>
搭建本地https
查看>>
云解析DNS产品优势与应用场景
查看>>
Vue路由
查看>>
分享:用promise封装ajax
查看>>
人工智能时代,教育如何做人工智能的“弄潮儿”?
查看>>
Spring Cloud构建分布式电子商务平台:服务消费(基础)
查看>>
随记:kickstart远程批量无人值守安装linux
查看>>
Linux: CentOS 7下搭建高可用集群
查看>>
数据库开发个人总结(ADO.NET小结)
查看>>
CHUCK手把手带你搞定OPENSTACK
查看>>