当前位置: 首页 > 工具软件 > Critical Mass > 使用案例 >

uva 580-Critical Mass(动态规划)

牟黎昕
2023-12-01

原题链接:点击打开链接

题意:一个栈中只能放入U和L,问存在连续3个以上U(危险组合)的个数为几个

说明:数据很小(n<=30)Σ( ° △ °|||)︴

解法一:

用总组合数-安全组合=危险组合。d[i]表示第i个位置以L结束的序列个数,所以就有d[i] = d[i - 1] + d[i - 2] + d[i - 3]。

直观的理解一下,设A(i)为第i个位置以L结束的序列,则A(i)=A(i-1)L+A(i-2)UL+A(i-3)UUL

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
using  namespace std;
typedef  long  long  ll;
const int inf=0x3f3f3f3f;
const int maxn=30;
int dp[maxn+5],n;
void  init(){
    dp[1]=2;
    dp[2]=4;
    dp[3]=7;
    for(int  i=4 ; i<=maxn ; i++){
        dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
//    #ifndef ONLINE_JUDGE
//	freopen("inM.txt", "r", stdin);
//    #endif
    init();
    while(scanf("%d",&n)&&n){
        int ans=pow(2,n);
        ans-=dp[n];
        printf("%d\n",ans);
    }
    return 0;
}

/******************************************************************我是萌萌哒的分割线(⊙ω⊙)******************************************************************************/

解法二:

     用dp。求出合法的数量,取补即可。

    设f(XY,n)为长度为0、结尾字符为XY的合法串个数,则有:

            f(UU,i)= f(LU,i-1);
            f(UL,i)= f(UU,i-1)+ f(LU,i-1);
            f(LU,i)= f(UL,i-1)+ f(LL,i-1);
            f(LL,i)= f(UL,i-1)+ f(LL,i-1);
    然后,求补即可(2^n - f(UU,n)- f(UL,n)- f(LU,n)- f(LL,n))。

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>

using namespace std;

int f[31][5];

int main()
{
    #ifndef ONLINE_JUDGE
	    freopen("inM.txt", "r", stdin);
    #endif
    for (int i = 0 ; i < 4 ; ++ i)
        f[2][i] = 1;
    for (int i = 3 ; i < 31 ; ++ i) {
        f[i][0] = f[i-1][2];
        f[i][1] = f[i-1][0]+f[i-1][2];
        f[i][2] = f[i][3] = f[i-1][1]+f[i-1][3];
    }

    int n;
    while (~scanf("%d",&n) && n) {
        if (n < 3)
            printf("0\n");  //注意少数情况的处理
        else {
            int ans = 1<<n;
            for (int i = 0 ; i < 4 ; ++ i)
                ans -= f[n][i];
            printf("%d\n",ans);
        }
    }
    return 0;
}



 类似资料: