【蓝桥杯官网试题 - 历届试题】格子刷油漆(dp)

题干:

问题描述

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


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

输入格式

  输入数据为一个正整数(不大于1000)

输出格式

  输出数据为一个正整数。

样例输入

2

样例输出

24

样例输入

3

样例输出

96

样例输入

22

样例输出

359635897

解题报告:

这是一个虽然可以预处理然后On求解但是比较懒的O(n^2)算法、、、

dp[i]代表以第1列的某一个格子为一个开始,往后涂i列的所有方法数。

dpp[i]代表以第1列的某一个格子为一个开始,先往右涂,的方法数。

对于dpp[i]显然等于dpp[i-1]*2,因为我可以选择下一列格子的上面那个或者下面那个。

对于dp[i],显然可以先向下走,这样就转化成dp[i-1]*2的问题了;显然也可以向右走,这样就是dpp[i-1]*2的问题了。但是忘了一种情况,可以先往右走一格,再倒退回来一格,再往右走一格,这样就变成了2*dp[i-2]的情况了,(盗个图)

也就是说我可以是

1->3->2->4->5....

1->3->2->4->6....

1->4->2->3->5....

1->4->2->3->6....

(不仔细想确实想不到啊。。。)

然后枚举终点xjb转移就行了。

AC代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
const ll mod = 1e9 + 7;
ll dp[MAX];//从某一列的随便一个格子开始,下一步往下涂的方案数。
ll dpp[MAX];//下一步往右涂的方案数
int main() {
	int n;
	dp[1] = 1; dpp[1] = 1; dp[2] = 6; dpp[2] = 2;
	for(int i = 3; i<=1000; i++) {
		dp[i] = ((dp[i-1] + dpp[i-1])*2)%mod + (dp[i-2]*2 * 2)%mod;
		dp[i] %= mod;

		dpp[i] = dpp[i-1]*2;
		dpp[i] %= mod;
	}
	while(~scanf("%d",&n)) {
		ll ans = 0,tmp1,tmp2,tmp;
		if(n == 1) {
			printf("2\n");
			continue;
		}
		for(int i = 2; i<=n-1; i++) {
			tmp1 = ((dpp[i-1]*2)%mod * dp[n-i]*2)%mod;
			tmp2 = ((dpp[n-i]*2)%mod * dp[i-1]*2)%mod;
			tmp = tmp1+tmp2;
			tmp *= 2;
			ans += tmp%mod;
			ans %= mod;
		}
		ans%=mod;
		ans += (dp[n]*4)%mod;
		printf("%lld\n",ans%mod);
	}

	return 0 ;
}

 

全部评论

相关推荐

Lorn的意义:你这标个前端是想找全栈吗?而且项目确实没什么含金量,技术栈太少了,边沉淀边找吧 现在学院本想就业好一点四年至少得高三模式两年加油吧
点赞 评论 收藏
分享
来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务