G.機器人
題意:
有n個機器人,每個機器人會讀入一個x,并傳回ax+b。
現在有一個數x和n個機器人,每個機器人有參數a和b。
請你排列機器人,使得最後的參數盡可能的大。
詢問最後的最大值。
題解:
兩種做法。
第一種:
化簡這個不等式:(a_1(a_2x+b_2)+b_1<a_2(a_1x+b_1)+b_2)
按照這個不等式對數組排序即可。
時間複雜度(O(nlogn))。
第二種:
觀察到n的範圍隻有20,狀壓DP。
(20^{20})會爆Long Long,是以要用__int128存。
// Problem: 機器人
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9986/G
// Memory Limit: 1048576 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
pair<int,int> a[maxn];
long long ans=0;
long long x;
int n;
bool cmp (pair<int,int> x,pair<int,int> y) {
return 1ll*x.first*y.second+x.second<1ll*y.first*x.second+y.second;
}
void print(__int128 x){
if(x>9)print(x/10);
putchar(x%10+'0');
}
int main () {
scanf("%d%d",&n,&x);
for (int i=1;i<=n;i++) scanf("%d%d",&a[i].first,&a[i].second);
sort(a+1,a+n+1,cmp);
__int128 ans=x;
for (int i=1;i<=n;i++) ans=ans*a[i].first+a[i].second;
print(ans);
}