首页 > 代码库 > hackerrank【Lego Blocks】:计数类dp
hackerrank【Lego Blocks】:计数类dp
题目大意：
修一个层数为n，长度为m的墙，每一层可以由长度为1、2、3、4的砖块构成。
每一层都在同一个长度处出现缝隙是方案非法的，问合法的方案数有多少种
思路：
先求出总方案，再减去所有非法的方案数
总方案数容易求得，略
非法方案数就不太好求了，由于需要判重，我们可以按照 " 最左边的缝隙 " 所在的位置给非法方案数分类
这样就不会有重复了！
具体见代码：
#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>#include<math.h>using namespace std;#define mod 1000000007long long n,m;long long dp[1010],a[1010],sum[1010];long long pow(long long a,long long b){ long long res=1; while(b) { if(b&1) { res*=a; res%=mod; } a*=a; a%=mod; b>>=1; } return res;}void solve(long long n,long long m){ a[1]=1; a[2]=2; a[3]=4; a[4]=8; for(int i=5;i<=n;i++) { a[i]=(a[i-1]+a[i-2]+a[i-3]+a[i-4])%mod; } for(int i=1;i<=n;i++) { sum[i]=pow(a[i],m); } dp[0]=0; for(int i=1;i<=n;i++) { dp[i]=sum[i]; for(int j=1;j<i;j++) { dp[i]-=dp[j]*sum[i-j]; dp[i]=(dp[i]%mod+mod)%mod; } } cout<<dp[n]<<endl;}int main(){ int t; scanf("%d",&t); while(t--) { cin>>n>>m; solve(m,n); } return 0;}
hackerrank【Lego Blocks】:计数类dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。