UVA580-Critical Mass

题意

有两种方块，L和U,有至少三个连续的U称为危险组合，问有多少个危险组合

solution：

至少这个概念比较难求，所以转化为（1ll<<n)-安全组合

dp[n][i]表示前n个数里以i个U结尾的个数

递推方程

dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
dp[i][1]=dp[i-1][0];
dp[i][2]=dp[i-1][1];

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<cstring>

 #define mp make_pair

 #define pb push_back

 #define first fi

 #define second se

 #define pw(x) (1ll << (x))

 #define sz(x) ((int)(x).size())

 #define all(x) (x).begin(),(x).end()

 #define rep(i,l,r) for(int i=(l);i<(r);i++)

 #define per(i,r,l) for(int i=(r);i>=(l);i--)

 #define FOR(i,l,r) for(int i=(l);i<=(r);i++)

 #define eps 1e-9

 #define PIE acos(-1)

 #define cl(a,b) memset(a,b,sizeof(a))

 #define fastio ios::sync_with_stdio(false);cin.tie(0);

 #define lson l , mid , ls

 #define rson mid + 1 , r , rs

 #define ls (rt<<1)

 #define rs (ls|1)

 #define INF 0x3f3f3f3f

 #define LINF 0x3f3f3f3f3f3f3f3f

 #define freopen freopen("in.txt","r",stdin);

 #define cfin ifstream cin("in.txt");

 #define lowbit(x) (x&(-x))

 #define sqr(a) a*a

 #define ll long long

 #define ull unsigned long long

 #define vi vector<int>

 #define pii pair<int, int>

 #define dd(x) cout << #x << " = " << (x) << ", "

 #define de(x) cout << #x << " = " << (x) << "\n"

 #define endl "\n"

 using namespace std;

 //**********************************

 const int maxn=;

 int n;

 ll dp[][];

 //**********************************

 void Init()

 {

     cl(dp,);

     dp[][]=dp[][]=dp[][]=dp[][]=;dp[][]=;

     FOR(i,,){

         dp[i][]=dp[i-][]+dp[i-][]+dp[i-][];

         dp[i][]=dp[i-][];

         dp[i][]=dp[i-][];

 //        dd(i);dd(dp[i][0]);dd(dp[i][1]);de(dp[i][2]);

     }

 }

 //**********************************

 int main()

 {

     Init();

     while(cin>>n,n){

         ll ans=;

         ans=dp[n][]+dp[n][]+dp[n][];

         printf("%lld\n",(1ll<<n)-ans);

     }

     return ;

 }

第二种实现方法

dp[i+j][1]+=dp[i][0];

dp[i+j][0]+=dp[i][1];

     /*************************************************************************

         > File Name: a.cpp

         > Author: QWX

         > Mail:

         > Created Time: Sun 30 Sep 2018 04:01:42 AM PDT

      ************************************************************************/

     //{{{ #include

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<map>

 #include<set>

 #include<string>

 #include<cstring>

 #include<complex>

 #include<bits/stdc++.h>

 #define mp make_pair

 #define pb push_back

 #define first fi

 #define second se

 #define pw(x) (1ll << (x))

 #define sz(x) ((int)(x).size())

 #define all(x) (x).begin(),(x).end()

 #define rep(i,l,r) for(int i=(l);i<(r);i++)

 #define per(i,r,l) for(int i=(r);i>=(l);i--)

 #define FOR(i,l,r) for(int i=(l);i<=(r);i++)

 #define eps 1e-9

 #define PIE acos(-1)

 #define cl(a,b) memset(a,b,sizeof(a))

 #define fastio ios::sync_with_stdio(false);cin.tie(0);

 #define lson l , mid , ls

 #define rson mid + 1 , r , rs

 #define ls (rt<<1)

 #define rs (ls|1)

 #define INF 0x3f3f3f3f

 #define LINF 0x3f3f3f3f3f3f3f3f

 #define ll long long

 #define ull unsigned long long

 #define dd(x) cout << #x << " = " << (x) << ","

 #define de(x) cout << #x << " = " << (x) << "\n"

 #define endl "\n"

     using namespace std;

     //}}}

 ll dp[][];

 int n;

 int main()

 {

     dp[][]=dp[][]=;

     FOR(i,,){

         FOR(j,,)dp[i+j][]+=dp[i][];

         FOR(j,,)dp[i+j][]+=dp[i][];

     }

     while(cin>>n,n)cout<<(1ll<<n)-dp[n][]-dp[n][]<<endl;

     return ;

 }

类似题目

The Debut Album

题意：

给你一个串的长度n,串由1,2组成，1连续不超过a个，2连续不超过b个，问有多少种这样的串,对1e9+7取模。

solution：

递推方程

往后补值：dp[i+j][1]+=dp[i][0];

　　　　　dp[i+j][0]+=dp[i][1];

向前取值：dp[i][1]+=dp[j][0];

　　　　　dp[i][0]+=dp[j][1];

 /*************************************************************************

     > File Name: j.cpp

     > Author: QWX

     > Mail:

     > Created Time: Fri 05 Oct 2018 08:58:42 PM PDT

  ************************************************************************/

 //{{{ #include

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<map>

 #include<set>

 #include<string>

 #include<cstring>

 #include<complex>

 //#include<bits/stdc++.h>

 #define mp make_pair

 #define pb push_back

 #define first fi

 #define second se

 #define vi vector<int>

 #define pii pair<int,int>

 #define pw(x) (1ll << (x))

 #define sz(x) ((int)(x).size())

 #define all(x) (x).begin(),(x).end()

 #define rep(i,l,r) for(int i=(l);i<(r);i++)

 #define per(i,r,l) for(int i=(r);i>=(l);i--)

 #define FOR(i,l,r) for(int i=(l);i<=(r);i++)

 #define eps 1e-9

 #define PIE acos(-1)

 #define cl(a,b) memset(a,b,sizeof(a))

 #define fastio ios::sync_with_stdio(false);cin.tie(0);

 #define lson l , mid , ls

 #define rson mid + 1 , r , rs

 #define ls (rt<<1)

 #define rs (ls|1)

 #define INF 0x3f3f3f3f

 #define LINF 0x3f3f3f3f3f3f3f3f

 #define ll long long

 #define ull unsigned long long

 #define dd(x) cout << #x << " = " << (x) << ","

 #define de(x) cout << #x << " = " << (x) << "\n"

 #define endl "\n"

 using namespace std;

 //}}}

 int n;

 const int maxn=5e5+;

 int dp[maxn][];

 const int mod=1e9+;

 inline int add(int a,int b){a+=b;if(a>mod)a-=mod;return a;}

 int main()

 {

     int n,a,b;

     cin>>n>>a>>b;

     cl(dp,);

     dp[][]=dp[][]=;

     FOR(i,,n){

         FOR(j,,a)dp[i+j][]=add(dp[i+j][],dp[i][]);

         FOR(j,,b)dp[i+j][]=add(dp[i+j][],dp[i][]);

     }

     cout<<add(dp[n][],dp[n][])<<endl;

     return ;

 }

巴特西

递推，求至少连续放置三个U的危险组合

UVA580-Critical Mass

题意

solution：

题意：

solution：

最新文章

热门文章