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;

}

巴特西

【JZOJ6350】考试(test)

description

analysis

code

最新文章

热门文章