http://acm.timus.ru/problem.aspx?space=1&num=1276
用 ans[numaa][numab][numba][numbb][0] 表示用 numaa個AA ?numab個AB? numba個BA ?numbb個BB?? 以 A為結尾的種類數量
用 ans[numaa][numab][numba][numbb][1] 表示用 numaa個AA? numab個AB? numba個BA ?numbb個BB?? 以 B為結尾的種類數量
然后根據結尾是A還是B 進行向后更新數量
代碼：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<queue>
#include<stack>
#include <iomanip>
using namespace std;
#define LL long long
const int INF=0x3f3f3f3f;
const int N=45;
LL ans[20005][2];
int aa,ab,ba,bb;
int F(int i,int j,int l,int r)
{
int x=r;
x+=(l*bb);
x+=(j*ba*bb);
x+=(i*ab*ba*bb);
return x;
}
int main()
{
//freopen("data.in","r",stdin);
int n,k;
while(cin>>n>>k)
{
ab=0;aa=0;ba=0;bb=0;
string stmp;
int locomotive;
cin>>stmp;
if(stmp=="AA") locomotive=0;
if(stmp=="AB") locomotive=1;
if(stmp=="BA") locomotive=2;
if(stmp=="BB") locomotive=3;
for(int i=1;i<=n;++i)
{
cin>>stmp;
if(stmp=="AA") ++aa;
if(stmp=="AB") ++ab;
if(stmp=="BA") ++ba;
if(stmp=="BB") ++bb;
}
++aa;++ab;++ba;++bb;
memset(ans,0,sizeof(ans));
if(locomotive==0||locomotive==2)
ans[0][0]=1;
else
ans[0][1]=1;
LL sum=0;
for(int i=0;i<aa;++i)
for(int j=0;j<ab;++j)
for(int l=0;l<ba;++l)
for(int r=0;r<bb;++r)
if(i+j+l+r<=k)
{
int x=F(i,j,l,r);
if(i+j+l+r==k)
{
if(locomotive==0||locomotive==1)
sum+=ans[x][0];
else
sum+=ans[x][1];
}
if(ans[x][0]!=0)
{
if(i+1<aa)
ans[F(i+1,j,l,r)][0]+=ans[x][0];
if(j+1<ab)
ans[F(i,j+1,l,r)][1]+=ans[x][0];
}
if(ans[x][1]!=0)
{
if(l+1<ba)
ans[F(i,j,l+1,r)][0]+=ans[x][1];
if(r+1<bb)
ans[F(i,j,l,r+1)][1]+=ans[x][1];
}
}
if(sum==0)
cout<<"NO"<<endl;
else
{cout<<"YES"<<endl;cout<<sum<<endl;}
}
return 0;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
