NOI’95 “同創杯”全國青少年信息學（計算機）奧林匹克競賽
分區聯賽復賽測試數據（初中組）

第五題

設在一排上有N個格子（N≤20），若在格子中放置有不同顏色的燈，每種燈的個數記為N1，N2，……Nk（k表示不同顏色燈的個數）。(顏色數<4)
放燈時要遵守下列規則：
①同一種顏色的燈不能分開；
②不同顏色的燈之間至少要有一個空位置。
例如：N=8（格子數）
R=2（紅燈數）
B=3（藍燈數）
放置的方法有： R-B順序，B-R順序, 放置的總數為12種。

程序要求：求出排列方案總數。

Input

數據輸入的方式為：
N
P1（顏色，為一個字母） N1（燈的數量）
P2 N2
……
Q（結束標記，Q本身不是燈的顏色）

Output

排列方案總數

Sample Input
8
R 2
B 3
Q
Sample Output
12

解析：
首先可以將同種顏色的燈的個數化為1個，即n-m+1，燈顏色種數為m；

那么燈之間一定有m-1個空格且每個燈占用一個空格，則剩下s=n-2*m+1個空格；

而燈旁邊有m+1個間隙；

可以考慮為s個空格插在m+1個間隙中，一個間隙可以插入0，1個或多個空格，那么可以用DFS來遍歷間隙即可

綜上：可將上面的問題就歸結為這樣一個數學模型：

將同一種顏色的燈歸到一起，看成一個；
dfs出一種顏色順序下的所有順序；
再將它乘上N種顏色的排列數N！；
即可得到總排列數。。。。

本題的難點在于DFS的理解和運用上。

代碼參考如下：

#include<iostream> using namespace std;int n,m,ans;void DFS(int k,int sum); int main() {while(cin>>n){ans=m=0;char c;int x;while(cin>>c&&c!='Q'){cin>>x;n-=x-1; ++m;cout<< "the total n is: "<<n<<endl;}int s=n-2*m+1,p=1;cout<<"the empty place is: "<<s<<endl;cout<<"the lamp has types is: "<<m<<endl;for(int i=1;i<=m;++i)p*=i; //m個種類的燈的全排列m+=1;DFS(1,s); //深度遍歷求得m+1個間隙中插入最多S個空格的方案數ans*=p;cout<<ans<<endl;}return 0; }void DFS(int k,int sum) {cout<<"the k is :"<<k<<endl;if(k==m||!sum){++ans;cout<<"the ans is:"<<ans<<endl;return;}for(int i=0;i<=sum;++i){DFS(k+1,sum-i);cout<<"the i is:"<<i<<endl;} }

ps:

DFS:深度優先搜索算法，是一種暴力搜索。該模型的理解相對有一些困難，算法的學習本身就比較抽象，結合典型的實例來幫助理解，這樣有助于事半功倍。

總結

以上是生活随笔為你收集整理的NOIP信息奥赛--1995“同创杯”初中复赛题题解（五）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。