Ant Counting POJ - 3046

本文主要是介绍Ant Counting POJ - 3046，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出T个蚂蚁种类，一共A只蚂蚁，要求算出蚂蚁按照S只到B只组队的组合数

Sample Input

3 5 2 3
1
2
2
1
3

Sample Output

10

思路：多重集组合数问题，dp[i][j] = i 种蚂蚁按照 j 只排列的组合总数

           if(j-1-a[i] >= 0)  dp[i][j] = dp[i][j-1] + dp[i-1][j] -dp[i-1][j-1-a[i]]

           else   dp[i][j] = dp[i][j-1] + dp[i-1][j]

           递推式推导：为了从i 种蚂蚁取出 j 只排列组合 可以 从i-1种蚂蚁取出j-k只排列组合后，从第 i 中蚂蚁中取出k只组合

           dp[i][j] = min(j,a[i])  ∑ k=0   dp[i-1][j-k]            // ∑前是上界，∑后是下界    理解哈

           min(j,a[i])  ∑ k=0   dp[i-1][j-k]   =   ( min(j-1,a[i])  ∑ k=0   dp[i-1][j-k] ) +  dp[i-1][j] - dp[i-1][j-1-a[i]]

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <fstream>
#include <set>
const long long MAX = 1e5+10;
#define INF 10000000
const int mod = 1e6;using namespace std;int dp[1010][MAX]; //前i种取j个的组合数//测试函数 
int main(){/*ifstream cin ("D:\\钢铁程序员\\程序数据\\053蚂蚁分队.txt");//从文件读取数据流，省去手动输入的麻烦 if(!cin){//读取如果失败 cout << "ERROR" << endl;}*/int T,A,S,B;int a[MAX]; //统计蚂蚁集合的数量 cin >> T >> A >> S >> B;for(int i=0; i<A; i++){int c;cin >> c;a[c]++;}int ans = 0;//依次求出分为S。。B小队的组合数 for(int i = 0; i <= T; ++i)dp[i][0] = 1;for(int i=1; i<=T; i++)for(int j=1; j<=A; j++){if(j-1-a[i] >= 0)dp[i][j] = (dp[i][j-1] + dp[i-1][j] -dp[i-1][j-1-a[i]]+mod)%mod;elsedp[i][j] = (dp[i][j-1] + dp[i-1][j]+mod)%mod;}for(int i=S; i<=B; i++)ans = (ans+dp[T][i]+mod)%mod;cout << ans << endl;//cin.close();//打开文件以后要关闭 return 0;
} 

 

这篇关于Ant Counting POJ - 3046的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---