P3711摆花
时间限制 : - MS 空间限制 : 65536 KB
评测说明 : 时限1000ms
问题描述
艺术馆门前将摆出许多花，一共有n个位置排成一排，每个位置可以摆花也可以不摆花。有些花如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种花数量无限，求摆花的方案数。
输入格式
输入共有1+m行：
第一行有两个用空格隔开的正整数n、m，m表示花的种类数。
接下来的m行，每行有m个字符1或0,若第i行第j列为1，则表示第i种花和第j种花不能排在相邻的位置，输入保证对称。（提示：同一种花可能不能排在相邻位置）。
输出格式
输出只有一个整数，为方案数（这个数字可能很大，请输出方案数除以1000000007的余数）
样例输入 1
2 2
0 1
1 0
样例输出 1
7
样例输入 2
3 3
0 0 0
0 1 0
0 0 1
样例输出 2
50
提示
样例说明
七种方案为(空，空)、（空，1）、（1、空）、（2、空）、（空、2）、（1,1）、（2,2）
100%的数据，1＜n≤1000000000，0＜m≤100。
其实我真的没有注意到原来艺术馆门前的花摆的这么讲究（因为感觉它们都是一个颜色）
题解
先讲讲动归（毕竟特供版，还是要打好基础）
所谓动归，就是确定某个状态dp[i]，并探讨i的值不同时dp之间的关系
说白了，就是找规律
但由于动归的规律一般都不会很直白地告诉你，所以我们一般需要把题目数学抽象化
然后得出类似于
dp[i]=dp[i-1]+dp[i-2]
之类的公式（这就是递推式）（所有数据的通解，并且一般需要递归）
递推式
首先,这道题目用动归(基本上所有摆成一排的东西都可以用动归敷衍了事)
然后我们就需要知道动归的递推式
由于这边有很多种花
想要用一个递推式表达不太可能
因为我们定状态时需要一个位置一个位置地讨论
所以我们规定dp[i]为摆花摆到第i个位置时地方案数
但由于dp[i]与dp[i-1]之间的关系不是很简单
比如,第1种花不能和第2种放在一起
那么递归式就应该为
对于第一种花,dp[i]=1*（第一种花的）dp[i-1]+0*dp[i-1]
所以我们的递推式也应该分类进行讨论
首先我们用动归的思维来进行分析
假设一共只有两种花,并且第一种与第二种是不能相邻的
那么在某一个空位上就有三种选择,第一种,第二种,或者不放花
按照动态规划的思维,我们假设已经知道了前n-1个位置放花的总方案数dp[n-1],求第n个位置放花的方案数dp[n]
那么,我们必须知道第n-1个位置放的是什么花
而简单的dp[n-1]表示的只是放到第n-1个位置总的方案数,无法得知放的是什么花
所以我们选择加一维数组
于是最新的状态为dp[f][n],表示在第n个位置上放上第f种花的总方案数
现在思考一下
我们如果已知dp[0][n-1],dp[1][n-1],dp[2][n-1]
f=0的时候(也就是不放花),因为不放花与其它两种没有冲突,所以我们可以选择在dp[1][n-1]后不放花,也可以选择在dp[2][n-1]后不放花,也可以在dp[0][n-1]后不放花
于是dp[0][n]= 1 *dp[0][n-1]+ 1 *dp[1][n-1]+ 1 *dp[2][n-1]
f=1的时候(放第1种花),根据上述思路,我们不能够在第2种花后面放第一种花,而其它两种方案都可行
于是dp[1][n]= 1 *dp[0][n-1]+ 1 *dp[1][n-1]+ 0 *dp[2][n-1]
f=2的时候(放第2种花),同上
于是dp[2][n]= 1 *dp[0][n-1]+ 0 *dp[1][n-1]+ 1 *dp[2][n-1]
这就是大概的思维过程
所以我们也可以推断出一个式子
如果已知当前的各种花的最大方案数为dp[0][n-1],dp[1][n-1],dp[2][n-1]...,dp[f][n-1]
那么对于当前讨论的花k,它前面一格的每种花为i
如果在用can[i]=1表示它可以接在某种花之后,用can[i]=0表示它不可以接在某种花之后
那么dp[k][n]=can[0]*dp[0][n-1]+can[1]*dp[1][n-1]+...
即can[i]为dp[i][n-1]的系数
转化为矩阵
那么我们定义矩阵
如果有k种花(第0种为不放花),且当前放到了第n个位置
矩阵状态为
dp[0][n],dp[1][n]...dp[k][n]
由上面的推导可得第二个矩阵的状态
第k列就应该是第k种花对应的can数组的值(注意此处为列)
结合到上一道3712的系数法来看这道题目
第二个矩阵的第k列其实就对应了dp[k][n]的递推式的系数
关于矩阵
我知道这对于初学者来讲确实很难理解,但是方法也是需要理解的，想要搞懂还请多次尝试理解
并且我确实很难再讲得更精细了
这道3711和3712其实都是为初学者写的(甚至可能没学过动归)
因为矩阵举例子实在是很累,所以我没有举太多例子
不过现在理解不到也没什么，反正何老板会讲动归的
动归转化成矩阵并不难，难的是动归本身
我会再更新几篇关于动归的题目来加深对递推式的理解
那么关于矩阵的构造，详细过程就此告一段落了
总结下来
对于矩阵1的第一行第k项
矩阵2中的第k列的各个数字对应的就是它的递推式的系数
你学到了么？？
附上代码（仅用于对答案）
#include <iostream>
#include <cstdio>
#include <cstring>
#define mod 1000000007;
using namespace std;
int n,m;
struct trix
{
long long x[][];
trix(){memset(x,,sizeof(x));}
trix operator *(const trix&y)
{
trix ans=trix();
for(int a=;a<=m;a++)
for(int b=;b<=m;b++)
for(int c=;c<=m;c++)
ans.x[a][b]+=(x[a][c]*y.x[c][b])%mod;
for(int a=;a<=m;a++)
for(int b=;b<=m;b++)
ans.x[a][b]=ans.x[a][b]%mod;
return ans;
}
void out()
{
long long ans=;
for(int i=;i<=m;i++)ans=(ans+x[][i])%mod;
printf("%lld",ans);
}
};
trix ori=trix(),add=trix();
void multi(int t)//矩阵快速幂
{
while(t)
{
if(t&)ori=ori*add;
add=add*add;
t>>=;
}
ori.out();
}
int main()
{
int c;
scanf("%d%d",&n,&m);
for(int a=;a<=m;a++)ori.x[][a]=add.x[][a]=add.x[a][]=;
for(int a=;a<=m;a++)
for(int b=;b<=m;b++)scanf("%d",&c),add.x[b][a]=-c;//以上三行都在建矩阵
multi(n-);
}
![[LeetCode]（面试题 17.21）直方图的水量[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)