题意：就5种盒子，给出每个盒子个数，盒子总数，每个人选择这个盒子的概率。求这个人选择哪个盒子取得第一个朋友的概率最大，最大多少
dp[N][sta]表示当前第N个人面临状态sta（选择盒子的状态可以用13进制数表示)时的概率，
那么转移就是dp[N][sta]=sum(dp[N-1][sta-1]*G[n][k]) (表示第N个人选择第k个盒子)
那么答案应该是max(P(第1个人选择i号盒子)/总状态概率)(i<=5)
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} #define MAXN 350000 #define MAXD 15 #define MAXB 10 double p[MAXD][MAXB],dp[MAXD][MAXN]; bool vis[MAXD][MAXN]; int N,res[MAXB],gift[MAXB]; double calcu(int cur,int st) { if (vis[cur][st]) return dp[cur][st]; vis[cur][st]=true; double ans=0; int sta=st; for (int i=5;i>0;i--) {res[i]=sta%13;sta/=13;} for (int i=1;i<=5;i++) if (res[i]) { res[i]--; sta=0; for (int j=1;j<=5;j++) sta=sta*13+res[j]; ans+=calcu(cur+1,sta)*p[cur][i]; res[i]++; } return dp[cur][st]=ans; } int main() { //freopen("sample.txt","r",stdin); int T; scanf("%d",&T); while (T--) { scanf("%d",&N); int sta=0; for (int i=1;i<=5;i++) { scanf("%d",&gift[i]);sta=sta*13+gift[i];} for (int i=1;i<=N;i++) for (int j=1;j<=5;j++) scanf("%lf",&p[i][j]); memset(vis,false,sizeof(vis)); vis[N+1][0]=true;dp[N+1][0]=1; double tmp=calcu(1,sta); double ans=-1.0,sym;int ide; for (int i=1;i<=5;i++) if (gift[i]) { gift[i]--; sta=0; for (int j=1;j<=5;j++) sta=sta*13+gift[j]; gift[i]++; sym=dp[2][sta]*p[1][i]/gift[i]; if (sym/tmp>ans) { ans=sym/tmp; ide=i; } } printf("%d %.3lf ",ide,ans); } return 0; }