Znzryb's Blog
0%

天梯赛选拔赛L2-2 逃离庄园

Posted on Edited on

思路讲解

image

这个是动态规划还是很明显的，但是是需要不等式优化的dp，因为裸的dp想到达到这道题目的O（n）时间复杂度还是有点困难的。

具体的来说，我们需要对机子进行排序，以让我们不需要考虑机子的顺序，按照排序顺序即可。

满足以下式子说明a1要排在前面。

a1(a2x+b2)+b1<a2(a1x+b1)+b2a1a2x+a1b2+b1<a1a2x+a2b1+b2a1b2+b1<a2b1+b2a1b2−b2<a2b1−b1a1−1b1<a2−1b2a_1(a_2x+b_2)+b_1 < a_2(a_1x+b_1) + b_2 \\a_1a_2x + a_1b_2 + b_1 < a_1a_2x + a_2b_1 + b_2 \\a_1b_2 + b_1 <a_2b_1 + b_2 \\a_1b_2 - b_2 < a_2b_1 - b_1 \\\cfrac{a_1 - 1}{b_1} < \cfrac{a_2 - 1}{b_2}

很明显，根据推导，该不等式具有传递性，因为a1，b1在一边，a2，b2在一边

然后动态规划部分其实就是从上面一个状态推下来，dp[i][j]表示考虑到第i个物品，选j个物品所能达到的最大值

这就是不考虑顺序（顺序已经是最优的情况）下，选K个物品时动态规划的套路

或者你还是理解不了，背包总理解吧？选K个物品不就是背包容量为K，每个物品重量为1吗？然后背包不也不用考虑顺序或者要求顺序已经最优吗？（其实是笔者自己不理解）

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// http://120.55.170.42/contest/1001/problem/L2-2
#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,K,T;
pll ab[MAXN];
ll dp[MAXN][15];

inline bool cmp(const pll &a,const pll &b){
	ll a1=a.fi,b1=a.se,a2=b.fi,b2=b.se;
	long double t2=(a2-1)*1.0l/b2,t1=(a1-1)*1.0l/b1;
	return t1<t2;
}

inline void solve(){
	cin>>N>>K;
	for(int i=1;i<=N;++i){
		cin>>ab[i].fi>>ab[i].se;
	}
	sort(ab+1,ab+1+N,cmp);
	for(int i=0;i<=K;++i){
		dp[0][i]=1;
	}
	for(int i=0;i<=N;++i){
		dp[i][0]=1;
	}
	// 注意到，其实k是很小的
	for(int i=1;i<=N;++i){
		ll a=ab[i].fi,b=ab[i].se;
		for(int j=1;j<=K;++j){
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]*a+b);
		}
	}
	cout<<dp[N][K]<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）