csp认证202109-4——之状态压缩dp加期望（记忆化搜索

https://www.acwing.com/problem/content/description/4012/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>
//#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"

const int N = 16;
const int M = 1<<16;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
double f[M][81];
double p[20];
//dp数组，但我们是用dfs函数得到计算答案的
//看到小范围根本没想到状态压缩dp，只想着dfs，当然如果你对记忆化搜索理解比较深
//也可以认为这就是dfs，如果是普通的dfs我没见过把状态当参数，所以还是要对状态压缩敏感。
//对于状态压缩dp，我们考虑把当前选了哪些牌设置为状态，为了判断什么时候能
//结束我们考虑还需要考虑当前剩余几张牌没抽到过，以及获得了多少硬币
double dfs(int state,int coin,int last){
	
	
//本质上last这一维是不需要的，因为state能把last求出来，但为了O（1）得到所以维护。
//这也提示我们状态压缩记忆化数组应该只要唯一确定状态的维度，但是搜索的时候可以增加参数优化
//上行的操作不影响时间复杂度
	auto& v=f[state][coin];
	if(v>=0)return v;
	if(last*m<=coin) return v=0;
	//由于v是引用，所以上一行需要在return前提前赋值，保证记忆化搜索。
	//表示到前状态距离目标状态只需要0次；
	v=0;
	for(int i=0;i<n;i++){
		if(state>>i &1){
			v+=p[i]*(dfs(state,coin+1,last)+1);
		}
		else {
			v+=p[i]*(1+dfs(state|1<<i,coin,last-1));
		}
	}
	return v;
}
void solve(){
	cin>>n>>m;
	memset(f,-1,sizeof f);
	for(int i=1;i<=n;i++)cin>>p[i-1];
	double ans=dfs(0,0,n);
	baoliu(ans,10);cout<<endl;
	
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
   t=1;

    while (t--) {
solve();
    }
    return 0;
}