CQYZ-OJ P1377 危险的组合

  • Post author:
  • Post category:其他


问题描述

有一些装有铀元素(用U表示)和铅元素(用L表示)的盒子,数量足够多,要求将N个盒子排成一行,但至少有M个U放在一起,有多少种方法?

输入格式

两个整数 N 和 M 。

输出格式

一个整数,表示方法数 。

思路:

因为该题满足局部最优导致整体最优,故动规

令 f i 为 有i个盒子能满足的方法数

则对于每一个新的箱子i

当除它以外的箱子(及之前的i-1个箱子)满足条件

那么显然无论新箱子放不放U都满足条件

提供 f(i-1)*2种方案

当除它以外的箱子无法满足条件时

则第i个箱子到第i-m-1个箱子都不得不放U

则提供 2

i-m-1

– f[i-m-1]


(注释:因为前i-1个箱子不满足条件,那么第i-m个箱子一定是放L的,那么这之前共有2

i-m-1

种放法,注意,因为这里是包含了第i-m-1个箱子前可以满足条件的情况的,那么应当减去f[i-m-1] 以求得之前i-1个箱子不满足条件的情况)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
ll f[65];
ll qpow[65];

void re0()   //求解2的幂
{
    qpow[0]=1;    
    for(int i=1;i<=n-m;i++)
     qpow[i]=qpow[i-1]*2;
    
    return ;
}

void solve()
{
    ll sum=1;
    memset(f,0,sizeof(f));
    f[m]=1;
    for(int i=m+1;i<=n;i++)
    {
        f[i]=f[i-1]*2+qpow[i-m-1]-f[i-m-1];
    }
    cout<<f[n]<<endl;
    
        return ;
}
int main(){
    
    scanf("%d%d",&n,&m);
    re0();
    
    solve();
    
    return 0;
}

转载于:https://www.cnblogs.com/Aloyd/p/8297954.html