首页 > 代码库 > UVa580 Critical Mass
UVa580 Critical Mass
DP计算没有连续的三个L的方案数，用总方案数减去不连续的方案数就是答案。
设dp[第i个][序列末尾有j个L]=方案数。
暴力转移，具体看代码。
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define LL long long 8 using namespace std; 9 LL dp[600][4];10 LL ans[600];11 LL total;12 int main(){13 int i,j;14 dp[1][0]=1;15 dp[1][1]=1;16 for(i=1;i<=30;i++){17 dp[i][1]+=dp[i-1][0];18 dp[i][2]+=dp[i-1][1];19 dp[i][0]+=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];20 }21 total=1;22 for(i=1;i<=30;i++){23 total<<=1;24 ans[i]=total-dp[i][0]-dp[i][1]-dp[i][2];25 }26 int n;27 while(scanf("%d",&n) && n){28 printf("%d\n",ans[n]);29 }30 return 0;31 }
UVa580 Critical Mass
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。