多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

國內最全IT社區平臺 聯系我們 | 收藏本站
阿里云優惠2
您當前位置:首頁 > php開源 > 綜合技術 > 6661 Equal Sum Sets(DP)

6661 Equal Sum Sets(DP)

來源:程序員人生   發布時間:2014-10-11 08:00:01 閱讀次數:3111次
Let us consider sets of positive integers less than or equal to n. Note that all elements of a set are
different. Also note that the order of elements doesnt matter, that is, both {3, 5, 9} and {5, 9, 3} mean
the same set.
Specifying the number of set elements and their sum to be k and s, respectively, sets satisfying the
conditions are limited. When n = 9, k = 3 and s = 23, {6, 8, 9} is the only such set. There may be
more than one such set, in general, however. When n = 9, k = 3 and s = 22, both {5, 8, 9} and {6, 7, 9}
are possible.
You have to write a program that calculates the number of the sets that satisfy the given conditions.
Input
The input consists of multiple datasets. The number of datasets does not exceed 100.
Each of the datasets has three integers n, k and s in one line, separated by a space. You may assume
1 ≤ n ≤ 20, 1 ≤ k ≤ 10 and 1 ≤ s ≤ 155.
The end of the input is indicated by a line containing three zeros.
Output
The output for each dataset should be a line containing a single integer that gives the number of the
sets that satisfy the conditions. No other characters should appear in the output.
You can assume that the number of sets does not exceed 231 ? 1.
Sample Input
9 3 23
9 3 22
10 3 28
16 10 107
20 8 102
20 10 105
20 10 155
3 4 3
4 2 11
0 0 0
Sample Output
1
2
0
20
1542
5448
1
0

0


DP遞推:dp[i][k][s]表示個數遞推關系:dp[i][k][s]=dp[i-1][k][s]+dp[i-1][k-1][s-i].

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=1000+100; int dp[21][11][156]; void init() { memset(dp,0,sizeof(dp)); dp[1][1][1]=1; for(int i=1;i<=20;i++) { dp[i][1][i]=1; dp[i][0][0]=1; } for(int i=2;i<=20;i++) { for(int k=1;k<=10;k++) { if(k>i) continue; for(int s=1;s<=155;s++) { int sum=0; // for(int j=1;j<i&&j<=k;j++) sum+=dp[i-1][k][s]; if(s>=i) sum+=dp[i-1][k-1][s-i]; dp[i][k][s]=sum; // if(i<=4&&s<10) // cout<<i<<" "<<k<<" "<<s<<" "<<sum<<endl; } } } // cout<<dp[4][2][5]<<endl; } int main() { init(); int n,k,s; while(~scanf("%d%d%d",&n,&k,&s)&&(n+k+s)) printf("%d ",dp[n][k][s]); return 0; }

另類似的HDU 2861 

Problem Description
Patti and Terri run a bar in which there are 15 stools. One day, Darrell entered the bar and found that the situation how customers chose the stools were as follows:
OOEOOOOEEEOOOEO
O means that the stool in a certain position is used, while E means that the stool in a certain position is empty (here what we care is not who sits on the stool, but whether the stool is empty).As the example we show above, we can say the situation how the 15 stools is used determines 7 intervals (as following):
OO E OOOO EEE OOO E O

Now we postulate that there are N stools and M customers, which make up K intervals. How many arrangements do you think will satisfy the condition?
 

Input
There are multi test cases and for each test case:
Each case contains three integers N (0<N<=200), M (M<=N), K (K<=20).
 

Output
For each test case print the number of arrangements as described above. (All answers is fit in 64-bit.)
 

Sample Input
3 1 3 4 2 4
 

Sample Output
1 2
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<limits.h> typedef long long LL; using namespace std; LL dp[201][201][22][2]; void init() { memset(dp,0,sizeof(dp)); dp[1][0][1][0]=1; dp[1][1][1][1]=1; for(int i=1;i<=200;i++) { dp[i][0][1][0]=1; dp[i][i][1][1]=1; } for(int i=2;i<=200;i++) { for(int j=1;j<=i;j++) { for(int k=1;k<=20&&k<=i;k++) { dp[i][j][k][0]=dp[i-1][j][k-1][1]+dp[i-1][j][k][0]; dp[i][j][k][1]=dp[i-1][j-1][k][1]+dp[i-1][j-1][k-1][0]; } } } // cout<<dp[12][13][15][0]<<endl; } int main() { int n,m,k; init(); while(~scanf("%d%d%d",&n,&m,&k)) printf("%I64d ",dp[n][m][k][0]+dp[n][m][k][1]); return 0; }


生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關閉
程序員人生
主站蜘蛛池模板: 性猛交xxxxx按摩中国 | 免费观看中文字幕 | 国产成人a一在线观看 | 免费网站在线看 | 亚洲欧美在线观看视频 | 国产亚洲精品激情一区二区三区 | 精品久久久久久亚洲 | 亚洲天堂二区 | 中文字幕日本在线视频二区 | 亚洲精品国产男人的天堂 | 欧美人与禽xoxo性伦交 | 精品国产一区二区三区国产馆 | 国产成人亚洲精品91专区手机 | freexx性| 亚洲黄色视屏 | 欧美第十页| 国产欧美日韩免费一区二区 | 午夜影院官网 | 欧美一区二区三区视频在线观看 | 永久免费网站 | 一区二区三区在线视频观看 | 亚洲午夜久久久精品影院视色 | www.国产在线观看 | 日本1区 | 自拍视频一区二区 | 久久综合久久综合久久 | 99国产精品欧美久久久久久影院 | 亚洲国产一区二区三区四区五区 | 精品一区二区三区18 | 欧美精欧美乱码一二三四区 | 人善交video 人善交videos欧美3 | 精品久久久99大香线蕉 | 国产一区二区三区在线 | freexx性日本| 国产一区二区亚洲精品天堂 | 国产亚洲一区二区三区在线观看 | 亚洲成人免费网站 | 三级性生活视频 | 国产免费一级片 | 日本国产亚洲 | 欧美性视频一区二区三区 |