国王游戏

本题需要高精，在此不细讲。

分析

我们考虑两个大臣\(p_1,p_2\)，它们站在国王\(p_0\)的身后，则这两个大臣有两种排列方案：

person	left	right
\(p_0\)	\(a_0\)	\(b_0\)
\(p_1\)	\(a_1\)	\(b_1\)
\(p_2\)	\(a_2\)	\(b_2\)

person	left	right
\(p_0\)	\(a_0\)	\(b_0\)
\(p_2\)	\(a_2\)	\(b_2\)
\(p_1\)	\(a_1\)	\(b_1\)

对于第一种情况，答案\(ans_1=\max(\frac{a_0}{b_1},\frac{a_0a_1}{b_2})\)

对于第二种情况，答案\(ans_2=\max(\frac{a_0}{b_2},\frac{a_0a_2}{b_1})\)

显然，\(\frac{a_0a_1}{b_2}>\frac{a_0}{b_2},\frac{a_0a_2}{b_1}>\frac{a_0}{b_1}\)

若\(ans_1<ans_2,\because \frac{a_0a_2}{b_1}>\frac{a_0}{b_1},\therefore \frac{a_0a_2}{b_1}\)必须\(>\frac{a_0a_1}{b_2}\)

即 \(\frac{a_2}{b_1}>\frac{a_1}{b_2}\) 即 \(a_1b_1<a_2b_2\)

因此，若\(a_1b_1<a_2b_2\)，就有\(p_1\)排在\(p_2\)前更优。

按照上述条件sort一遍，再计算答案即可。

Code

#include
    
     #define maxn 4010using namespace std;class hp{　　public:    int a[maxn];    hp(){memset(a,0,sizeof(a));}    void clear(){memset(a,0,sizeof(a));}    hp(int x){        clear();        while(x){            a[++a[0]]=x%10;            x/=10;        }        while(a[a[0]]==0&&a[0])a[0]--;    }    hp& operator=(int x){        clear();        while(x){            a[++a[0]]=x%10;            x/=10;        }        while(a[a[0]]==0&&a[0])a[0]--;        return *this;    }    short cmp(const hp& x){        if(a[0]>x.a[0])return 1;        if(a[0]
     
      =1;i--){            if(a[i]>x.a[i])return 1;            if(a[i]
      
       (const hp& x){        return cmp(x)==1;    }    bool operator==(const hp& x){        return cmp(x)==0;    }    bool operator<(const hp& x){        return cmp(x)==-1;    }    bool operator>=(const hp& x){        return !(*this
       
        x);    }        hp operator-(const hp& x){        hp a=*this,c;        c.a[0]=a.a[0]>x.a[0]?a.a[0]:x.a[0];        for(register int i=1;i<=c.a[0];i++) {            c.a[i]+=a.a[i]-x.a[i];            if(c.a[i]<0){c.a[i]+=10;a.a[i+1]--;}        }        while(c.a[c.a[0]]==0&&c.a[0])c.a[0]--;        return c;    }    hp operator*(const hp& x){        hp c;        for(register int i=1;i<=a[0];i++){            for(register int j=1;j<=x.a[0];j++){                 c.a[i+j-1]+=a[i]*x.a[j];            }        }        c.a[0]=a[0]+x.a[0];        for(register int i=1;i<=c.a[0];i++){            if(c.a[i]>=10){                c.a[i+1]+=c.a[i]/10;                c.a[i]%=10;            }        }        while (c.a[c.a[0]]==0&&c.a[0]>0)c.a[0]--;        return c;    }    hp operator/(const int& x){        hp c;        int t=0,s=0;        bool flag=1;        for(register int i=a[0];i>=1;i--){            t=s*10+a[i];            if(t/x>0||t==0){                c.a[++c.a[0]]=t/x;                s=t%x;                flag=0;            }            else{                s=t;                if(!flag)c.a[++c.a[0]]=0;            }        }        reverse(c.a+1,c.a+c.a[0]+1);        return c;    }};struct node{    int a,b;};node a[1001];bool cmp(node x,node y){    return x.a*x.b
        
         =1;i--)　　　　putchar(ans.a[i]+'0');　　return 0;}

补充题目：打CF

题意

一场CF比赛，时间为\(T\)分钟，有\(N\)道题，可以在比赛时间内的任意时间提交代码

第\(i\)道题的分数为\(maxPoints[i]\),题目的分数随着比赛的进行，每分钟减少\(pointsPerMinute[i]\)

这是一场比较dark的CF，分数可能减成负数

已知第\(i\)道题需要花费\(requiredTime[i]\)的时间解决

请问最多可以得到多少分

数据范围

\(1\le N\le 50,1\le T\le 100000,\)

\(1\le maxPoints[i],pointsPerMinute[i],requiredTime[i]\le 100000\)

分析

贪心思维题。

声明：在下面的分析中，我们约定

#define a maxPoints#define b pointsPerMinute#define c requiredTime

我们考虑两道题\(p_1,p_2\)，则先做\(p_1\)再做\(p_2\)能获得的分数为\[a_1-b_1c_1+a_2-b_2(c_1+c_2)\]先做\(p_2\)再做\(p_1\)能获得的分数为\[a_2-b_2c_2+a_1-b_1(c_2+c_1)\]

答案为\(ans_1,ans_2\)

若\(ans_1<ans_2\)，则

\(a_1-b_1c_1+a_2-b_2(c_1+c_2)<a_2-b_2c_2+a_1-b_1(c_2+c_1)\)，

\(<=> b_2c_1>b_1c_2\)

而\(ans_1<ans_2\)代表\(p_2\)放在\(p_1\)前更优，因此，使得\(p_1\)放在\(p_2\)前更优的条件是\[b_2c_1<b_1c_2\]

按照此条件对每一道题排序。

设做掉题目\(p_i\)的时刻为\(time\)，则\(p_i\)的实际得分为\[a_i-b_i* time\]

但由于比赛有时间限制，且题目最终得分可能为负数，因此，需要使用01背包来选择。转移方程：

\[dp[j]=dp[j-c[i]]+a[i]-b[i]* j\]

Code

#include
    
     #define maxn 55#define maxt 100005using namespace std;typedef long long D;inline D max(D x,D y){return x>y?x:y;}D a[maxn],b[maxn],c[maxn],tot,dp[maxt],ans;int cnt,n,t[maxn];bool cmp(int i,int j){　　return b[j]*c[i]
     
      =c[t[i]];j--){            dp[j]=max(dp[j],dp[j-c[t[i]]]+a[t[i]]-b[t[i]]*j);            ans=max(ans,dp[j]);        }    }　　printf("%lld\n",ans);　　return 0;}