本文主要是介绍Codeforces Round #594 (Div. 2) Ivan the Fool and the Probability Theory(DP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:https://codeforces.com/contest/1248/problem/C
题目大意:n*m的长方形中,一共有两种颜色,问每一个块相邻最多有一个与之相同颜色的块的染色方案数
题目思路:想了好久想不出来..真的丢人啊!挺水的一个题.......首先我们可以发现,如果有相邻两块颜色一样,那么他们下一行一定是确定的,因为这两块的下面两个块颜色不能与之相同,直角是不能出现的。然后就可以发现,无论旁边是啥颜色,都会变成与之想反,啥意思呢,简单地说就是,第一行如果存在相邻两块颜色一样,那么这个图形整个的图案就确定了。
但是有一种特殊情况,那就是交错出现黑和白,这种情况下,下面有时候是可以与上面相同的,也就是这种情况下图案不唯一。但是这也不是个问题,因为列上满足要求的方法跟行一样,只要你能保证每一列中都不要出现相邻超过三个相同颜色就行,因为横着都是交错出现,不用担心。所以问题就转换成了,如果只有一行的话,一共有几种方案呢?
这就是一个非常非常非常基础的dp,菜鸡我居然没写出来!!!真的要检讨....设dp[i][0]为第i个填白色的方案数,dp[i][1]表示第i个填黑色的方案数,那么显而易见,dp[1][0]=dp[1][1]=1(只有一个格子,又规定了颜色,肯定只有一种鸭!),dp[2][0]=dp[2][1]=2(两个格子的话,不管第二个啥颜色,第一个都能乱填,反正两个格子没法出现三个一样的情况),然后就是dp[i][0]=dp[i-1][1]+dp[i-2][1](当前是白色的话,要么前一个是黑色,要么前前个是黑色,前前前个才是黑色话就出现三个白色,就歇逼了,所以..后面那个原理一样),dp[i][1]=dp[i-1][0]+dp[i-1][0],二者合体,发现dp[i][0]+dp[i][1]=dp[i-1][0]+dp[i-1][0]+dp[i-1][1]+dp[i-2][1],那就直接合体,dp[i]=dp[i-1]+dp[i-2]
所以就是,一列m个有dp[m]种情况,其中要踢掉黑白相间的两种情况,这两种情况所占的就是n行的情况数,为dp[n],所以答案就是dp[n]+dp[m]-2
以下是代码:
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
const int MAXN = 1e5+5;
const int MOD = 1e9+7;
ll n,m;
ll dp[MAXN];
int main()
{dp[1]=2,dp[2]=4;rep(i,3,1e5)dp[i]=(dp[i-1]+dp[i-2])%MOD;while(cin>>n>>m){cout<<(dp[n]+dp[m]-2+MOD)%MOD<<endl;}return 0;
}
这篇关于Codeforces Round #594 (Div. 2) Ivan the Fool and the Probability Theory(DP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!