打开APP
userphoto
未登录

开通VIP,畅享免费电子书等14项超值服

开通VIP
蓝桥杯 格子刷油漆
问题描述

  X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形(如下图所示),现需要把这些格子刷上保护漆。

  

你可以从任意一个格子刷起,刷完一格,可以移动到和它相邻的格子(对角相邻也算数),但不能移动到较远的格子(因为油漆未干不能踩!)
  比如:a d b c e f 就是合格的刷漆顺序。
  c e f d a b 是另一种合适的方案。
  当已知 N 时,求总的方案数。当N较大时,结果会迅速增大,请把结果对 1000000007 (十亿零七) 取模。

输入格式
  输入数据为一个正整数(不大于1000)
输出格式
  输出数据为一个正整数。
样例输入
2
样例输出
24
样例输入
3
样例输出
96
这道题,根据数据量便可得知,使用的算法应该是动态规划,难点在于需要从第一个刷漆的格子的位置,将整体分成左右两半, 先刷一半,再刷另一半
dp[i][0]表示从第i个格子出发,刷满前i个格子后,最后回到第i个格子的方法数, dp[i][1]表示从第i个格子出发,刷满前i个格子后没有回到第i个格子的方法数。
下面是我的ac代码:
 1 #include<iostream> 2 using namespace std; 3 #define MAX 1020 4 long long dp[MAX][2],ans; 5 int main(){ 6     int m; 7     cin>>m; 8     dp[1][0]=2;dp[1][1]=0; 9     dp[2][0]=4;dp[2][1]=8;10     for(int i=3;i<MAX;i++){11         dp[i][0]=(dp[i-1][0]*2)%1000000007;12         dp[i][1]=2*(dp[i-1][0]+dp[i-1][1])%1000000007+4*(dp[i-2][0]+dp[i-2][1])%1000000007;13     }14     //从两端开始回到两端 以及从两端开始不回到两端 15     ans=2*(dp[m][0]+dp[m][1])%1000000007;16     //此处累加遍历第一个被刷的格子的列 17     for(int i=2;i<m;i++){18         //从中间第i位置开始先右后左 19         ans+=(dp[i][0]*(dp[m-i][0]+dp[m-i][1]))%1000000007;20         //从中间第i位置开始先左后右 21         ans+=(dp[m-i+1][0]*(dp[i-1][1]+dp[i-1][0]))%1000000007;22         ans%=1000000007;23     }24     cout<<ans<<endl;25     return 0;26 }

测评结果:

  

本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请点击举报
打开APP,阅读全文并永久保存 查看更多类似文章
猜你喜欢
类似文章
【热】打开小程序,算一算2024你的财运
HDU 1176 免费馅饼
连续子数组的最大和
《计算机算法设计与分析》第二版 王晓东 “最大m字段和优化函数”——P57注释
371,背包问题系列之-基础背包问题
买卖股票的最佳时机三
运筹学教学|动态规划例题分析(一)
更多类似文章 >>
生活服务
热点新闻
分享 收藏 导长图 关注 下载文章
绑定账号成功
后续可登录账号畅享VIP特权!
如果VIP功能使用有故障,
可点击这里联系客服!

联系客服