# CF97C Winning Strategy

### 倍增floyd

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define maxn 205
#define ll long long
using namespace std;
int n,cur,pre,m,cnt;
double inf,p[maxn],ans,tim;
struct matrix
{
double a[maxn][maxn];
void init(){memset(a,0xc2,sizeof(a));}
double* operator [] (int x){return a[x];}
matrix operator * (matrix x)
{
matrix y;y.init();
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=m;k++)
if(a[i][k]!=inf&&x[k][j]!=inf)
y[i][j]=max(y[i][j],a[i][k]+x[k][j]);
return y;
}
}mat[35],f;
int main()
{
//freopen("blasphemy.in","r",stdin);
//freopen("blasphemy.out","w",stdout);
cin>>n;m=n<<1;
for(int i=0;i<=n;i++)scanf("%lf",&p[i]);
for(int i=0;i<=30;i++)mat[i].init();f.init();
inf=f[0][0];f[0][0]=0;
for(int i=0;i<=m;i++)//转移矩阵
for(int j=0;j<=n;j++)
{
int k=i+n-j-j;
if(i-j>=0&&k>=0&&k<=m)mat[0][i][k]=max(mat[0][i][k],p[j]);
}
cnt=1;pre=1;
for(int c=1;cnt<=30;c<<=1,cnt++)
{
for(int i=0;i<=m;i++)
if(f[cur][i]!=inf)
{
for(int j=0;j<=m;j++)
if(mat[cnt-1][i][j]!=inf)
f[pre][j]=max(f[pre][j],f[cur][i]+mat[cnt-1][i][j]);
f[cur][i]=inf;
}
tim+=c;mat[cnt]=mat[cnt-1]*mat[cnt-1];swap(cur,pre);
for(int i=0;i<=m;i++)ans=max(ans,f[cur][i]/tim);
}
printf("%.10lf\n",ans);
return 0;
}

### 分数规划

$ans<=\frac{a_0p_0+a_1p_1+a_2p_2+...}{a_0+a_1+a_2+...}\a_0(ans-p_0)+a_1(ans-p_1)+...<=0$

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define maxn 305
#define maxm 500005
#define ll long long
using namespace std;
int to[maxm],cnt,m;
double p[maxn],mid,w[maxm],dis[maxn];
const double eps=1e-10;
queue<int> q;
{
to[cnt]=v;w[cnt]=ww;
}
bool spfa(int s)
{
dis[s]=0;while(!q.empty())q.pop();
q.push(s);vis[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();++cn[u];
vis[u]=1;o[u]=0;if(cn[u]==m)return 1;
{
int v=to[i];
if(dis[v]>dis[u]+w[i]+mid)
{
dis[v]=dis[u]+w[i]+mid;
if(!o[v])q.push(v),o[v]=1;
}
}
}
return 0;
}
bool check()
{
memset(o,0,sizeof(o));
memset(vis,0,sizeof(vis));
memset(cn,0,sizeof(cn));
for(int i=0;i<=m;i++)dis[i]=1e15;
for(int i=0;i<=m;i++)
if(!vis[i])if(spfa(i))return 1;
return 0;
}
int main()
{
//freopen("blasphemy.in","r",stdin);
//freopen("blasphemy.out","w",stdout);
cin>>n;m=n*2;
for(int i=0;i<=n;i++)scanf("%lf",&p[i]);
for(int i=0;i<=m;i++)
for(int j=0;j<=n;j++)
{
int k=i+n-j-j;
}
double l=0,r=1;
while(r-l>eps)
{
mid=(l+r)*0.5;
if(check())l=mid;
else r=mid;
}
printf("%.10lf\n",l);
return 0;
}

### 结论

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define maxn 205
#define ll long long
using namespace std;
int n;
double c[maxn],p[maxn],ans;
int main()
{
//freopen("blasphemy.in","r",stdin);
//freopen("blasphemy.out","w",stdout);
cin>>n;
for(int i=0;i<=n;i++)scanf("%lf",&p[i]);
for(int i=0;i<=n;i++)c[i]=fabs(n-2*i);
for(int i=0;i<=(n-1)/2;i++)
for(int j=(n-1)/2+1;j<=n;j++)
ans=max(ans,(c[j]*p[i]+c[i]*p[j])/(c[j]+c[i]));
printf("%.12lf",ans);
return 0;
}

CF97C Winning Strategy

(0)
(0)

0条