首页 > 其他 > 详细

UVA 580 Critical Mass

时间:2017-08-18 21:54:01      阅读:193      评论:0      收藏:0      [点我收藏+]

https://vjudge.net/problem/UVA-580

 

题意:一堆U和L,用n个排成一排,问至少有3个U放在一起的方案数

 

f[i] 表示 至少有3个U放在一起的方案数

g[i] 表示没有3个U放在一起的方案数

状态转移:

g[i]=2^i-f[i]

枚举 第一次出现3个U的位置j,那么j-1一定是L,前j-2个一定没有3个U放在一起,第j+2个往后随便放

所以 f[i]=2^(i-3) + Σ g[i-2]*2^(i-j-2) 

2^(i-3) 是当i=1时,后面的Σ从2开始

#include<cstdio>
#include<cmath>
using namespace std;
int g[31],f[31];
int main()
{
    int n;
    g[0]=1; g[1]=2; g[2]=4;
    while(scanf("%d",&n)!=EOF)
    {
        if(!n) return 0;
        if(n<=2) { printf("0\n"); continue; }
        for(int i=3;i<=n;i++) 
        {
            f[i]=pow(2,i-3);
            for(int j=2;j<=i-2;j++) f[i]+=g[j-2]*pow(2,i-j-2);
            g[i]=pow(2,i)-f[i];
        }
        printf("%d\n",f[n]);
    }
}

 

UVA 580 Critical Mass

原文:http://www.cnblogs.com/TheRoadToTheGold/p/7392249.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!