CCF-CSP-202109-4-收集卡牌

原题链接
满分代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef double LL;

const int N = 1<<16,M = 6;
int n,k;
LL a[16];
LL f[N][16*6];  //记忆化搜索,期望,   状态和钱
bool g[N][16*6];

LL dfs(int state,int money,int len){ //表示手中还没有的牌的数量
    if(g[state][money]){  //说明这种情况已经计算过
        return f[state][money];
    }
    if(state==(1<<n)-1){     //到叶子节点了
        return 0;
    }
    if(money>=len*k){          //钱够买剩余全部了
        return 0;
    }
    LL res=0;
    for (int i = 0; i < n; i ++ ){
        int c = (state>>i)&1;
        if(!c){ //找手中还没有的牌
            LL t = dfs(state|(1<<i),money,len-1);
            res += (t+1)*a[i];
        }else{
            LL t = dfs(state,money+1,len);
            res += (t+1)*a[i];
        }
    }
    g[state][money] = true;
    f[state][money] = res;
    return res;
}


int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i ++ ){
        cin >>a[i];
    }
    LL t = dfs(0,0,n);
    printf("%.10lf",t);
}