贪心是一种奇妙的算法，能将(O(n^2))、(O(n^3))的dp，(O(2^n))、(O(n!))的爆搜直接化成(O(n))。
国王游戏 link
本题需要高精，在此不细讲。
分析
我们考虑两个大臣(p_1,p_2)，它们站在国王(p_0)的身后，则这两个大臣有两种排列方案：
1
| person | left | right |
|---|---|---|
| (p_0) | (a_0) | (b_0) |
| (p_1) | (a_1) | (b_1) |
| (p_2) | (a_2) | (b_2) |
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,ecause frac{a_0a_2}{b_1}>frac{a_0}{b_1}, herefore 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<cstdio>
#define maxn 4010
using 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]<x.a[0])return -1;
for(register int i=a[0];i>=1;i--){
if(a[i]>x.a[i])return 1;
if(a[i]<x.a[i])return -1;
}
return 0;
}
bool operator>(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);
}
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<y.a*y.b;
}
void checkmax(hp& x,hp y){
if(x<y)x=y;
}
int main(){
int n;scanf("%d",n);
for(register int i=0;i<=n;i++){
scanf("%d%d",a[i].a,a[i].b);
}
sort(a+1,a+n+1,cmp);
hp ans=0,ji=a[0].a;
for(register int i=1;i<=n;i++){
checkmax(ans,ji/a[i].b);
ji=ji*a[i].a;
}
if(ans.a[0]==0)putchar('0');
else for(register int i=ans.a[0];i>=1;i--)
putchar(ans.a[i]+'0');
return 0;
}
补充题目：打CF
题意
一场CF比赛，时间为(T)分钟，有(N)道题，可以在比赛时间内的任意时间提交代码
第(i)道题的分数为(maxPoints[i]),题目的分数随着比赛的进行，每分钟减少(pointsPerMinute[i])
这是一场比较dark的CF，分数可能减成负数
已知第(i)道题需要花费(requiredTime[i])的时间解决
请问最多可以得到多少分
数据范围
(1le Nle 50,1le Tle 100000,)
(1le 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背包来选择。转移方程：
Code
#include<cstdio>
#define maxn 55
#define maxt 100005
using 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]<b[i]*c[j];
}
int main(){
scanf("%d%lld",n,tot);
for(int i=1;i<=n;i++)scanf("%lld",a[i]);
for(int i=1;i<=n;i++)scanf("%lld",b[i]);
for(int i=1;i<=n;i++)scanf("%lld",c[i]),t[i]=i;
sort(t+1,t+n+1,cmp);
for(int i=1;i<=n;i++){
for(int j=tot;j>=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
",ans);
return 0;
}