description
analysis
对于\(n=0\)的点，直接模拟就好了
状压\(DP\)，设\(f[i][j][S]\)表示到第\(i\)题、连续\(GG\)了\(j\)题、喝的饮料集合为\(S\)的最大答案
由于一题可以喝多瓶饮料所以转移需要枚举\(S\)的子集\(SS\)来转移
然后转移比较显然但是细节恶心
我不会告诉你我一共打了三个DP然后调出来其中一个才切的
code
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<iostream>
#define MAXN 105
#define MAX 500005
#define ha 19260817
#define db double
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)using namespace std;db f[MAXN][MAXN][3000],val[3000][3000];
ll x[MAX],yy[MAX],y[MAX],down[MAX],a[MAX],dif[MAX];
ll n,m,k,last;
db ans;inline ll read()
{ll x=0,f=1;char ch=getchar();while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
inline db sqr(db x){return x*x;}
inline db max(db x,db y){return x>y?x:y;}
inline db min(db x,db y){return x<y?x:y;}
int main()
{freopen("T1.in","r",stdin);//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);n=read(),m=read(),k=read();fo(i,1,n)x[i]=read();fo(i,1,m)yy[i]=read();fo(i,1,k-1)down[i]=read();fo(i,1,k)a[i]=read(),y[i]=yy[read()],dif[i]=read();if (n==0){db anss=0;fo(i,1,k){db prob=a[i]*(1-sqr(max(0,1-1.0*y[i]*(last?(1.0-down[i-last]/100.0):1)/dif[i])));if (prob<0.64*a[i])last=i;anss+=prob;}printf("%.2lf\n",anss);return 0;}fo(i,0,k)fo(j,0,k)fo(l,0,(1<<n)-1)f[i][j][l]=-ha;f[0][0][(1<<n)-1]=0;fo(S,0,(1<<n)-1){for (reg SS=S;SS>=0;SS=(SS-1)&S){val[S][SS]=1.0;fo(i,1,n)if ((S&(1<<(i-1))) && (!(SS&(1<<(i-1)))))val[S][SS]*=1+x[i]/100.0;if (!SS)break;}}fo(i,1,k){fo(j,0,i){fo(S,0,(1<<n)-1)if (f[i-1][j][S]>=0){for (reg SS=S;SS>=0;SS=(SS-1)&S){db pro=val[S][SS];if (j){db tmp=a[i]*(1-sqr(max(0,1-1.0*(y[i]*pro*(1-down[j]/100.0))/dif[i])));if (tmp>=0.64*a[i])f[i][j+1][SS]=max(f[i][j+1][SS],f[i-1][j][S]+tmp);else f[i][1][SS]=max(f[i][1][SS],f[i-1][j][S]+tmp);}else{db tmp=a[i]*(1-sqr(max(0,1-1.0*(y[i]*pro)/dif[i])));if (tmp>=0.64*a[i])f[i][0][SS]=max(f[i][0][SS],f[i-1][0][S]+tmp);else f[i][1][SS]=max(f[i][1][SS],f[i-1][0][S]+tmp);}if (!SS)break;}}}}fo(i,0,k)fo(j,0,(1<<n)-1)ans=max(ans,f[k][i][j]);printf("%.2lf\n",ans);return 0;
}
