首页 > 代码库 > 玲珑杯 #10 A dp递推
玲珑杯 #10 A dp递推
A. Black and White
题意：n个格子排在一行，每个格子里都有一枚白棋或一枚黑棋。限制：不能有连续a枚黑棋或连续b枚白棋，问有多少种方案。
tags：一开始还以为是组合数学，没想到又是dp。这mmp的还是签到题
考虑长度为 i 的合法序列与长度为 i−1 的合法序列有什么关系。定dp[i][black] 为有 i 枚棋子且最后一枚是黑色的合法方案数量，g[i]为有 i 枚棋子的合法方案数量。现假设前面 i-1 枚棋都是合法的，在 i 位置加一枚黑棋，唯一不合法的情况就是最后的a枚棋子全是黑色，即g[i]=g[i-1]-dp[i-a][white]。白棋同理，递推到g[n]即是答案。
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define FF(i,a,b) for (int i=a;i<=b;i++)#define F(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 2e6+10, mod=1e9+7;int a, b, n, T;ll dp[N][2], g[N];int main(){ scanf("%d", &T); while(T--) { scanf("%d %d %d", &a, &b, &n); dp[0][0]=dp[0][1]=1, g[0]=1; FF(i,1,n) { if(i-a>=0) dp[i][0]=g[i-1]-dp[i-a][1]; else dp[i][0]=g[i-1]; if(i-b>=0) dp[i][1]=g[i-1]-dp[i-b][0]; else dp[i][1]=g[i-1]; g[i]=(dp[i][0]+dp[i][1])%mod; } printf("%lld\n", (g[n]+mod)%mod); } return 0;}
玲珑杯 #10 A dp递推
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。