本文共 2249 字,大约阅读时间需要 7 分钟。
题意:一个人N门课程的总成绩为T,每门课程的最低成绩为P,求一共有多少种可能的分配方法。
题解:可以先求出超出的部分 T = T - n*p;剩余的相当于n个里面每个科目放0,1分等。
这题我只懂了递推,不懂组合数学,看来太弱了
dp[i][j] = dp[i-1][0] + dp[i-1][1] +......+d[[i-1][j];表示前i个盒子放j个球的方法
#include组合数学#include #include #include using namespace std;typedef long long LL;LL dp[80][80];int main(){ int t,n,T,p; cin >> t; while(t--){ cin >> n >> T >> p; T = T - n * p; memset(dp,0,sizeof(dp)); for(int i = 0;i <= n;i++) dp[i][0] = 1; for(int i = 1;i <= n;i++){ for(int j = 1;j <= T;j++){ for(int k = 0;k <= j;k++){ dp[i][j] += dp[i-1][k]; } } } cout << dp[n][T] << endl; }}
把T分分成T份放入到n个科目中,相当于把T个球放到n个盘子中,用多少种方法?(求大神解释|隔板法俺不懂啊)
#includetypedef long long LL;LL C(LL n, LL k) { if(n - k < k) k = n - k; LL ans = 1; for(int i = 1; i <= k; i++) ans = ans * (n - i + 1) / i; return ans;}int main() { int cas; LL n, t, p; scanf("%d", &cas); while(cas--) { scanf("%lld%lld%lld", &n, &t, &p); t = t - n * p; LL ans = C(n + t - 1, n - 1); printf("%lld\n", ans); } return 0;}
隔板法:
转载地址:http://xdsgi.baihongyu.com/