#C241008B. PolarSea与IOI
标签（Label）
- 动态规划
- 斜率优化
网址（Website）
题解（Solution）
$\qquad$很容易发现，如果要做完一道 $a_i = x$ 的题目，就必须把所有 $a_j>x$ 的题目全部做 $x$ 分钟，发现 $n$ 的值为 $2000$ ，考虑动态规划。
$\qquad$ 令 $f_{i,k}$ 表示当前点为 $i$ ，已经做了 $k$ 道题的最小分钟数，则有 $f_{i,k} = (i-j)\times a_i +f_{j,k-1}$ 。时间复杂度 $O(Tn^2m)$ ，可以拿一点暴力分。
$\qquad$考虑使用斜率优化，转化为 $f_{j,k-1} = -a_i\times j\ +\ a_i\times i + f_{i,k}$ ，对应 $y=k\times x+b$ ，要最小化 $f_{i,k}$ ，便要使该函数截距最小，简单推理发现要满足 $ktail<-a[i]$ 且 $khead<id$ 。
出题者题解
算法分析
由于最坏情况自己能求出来，所以实时知道自己过了哪些题只能判断当前是否不是最坏情况，那么我们不用管知道自己过了哪些题对策略的影响，就当必然是最坏情况即可。
我们把 $a_i$ 排序，设第 $i$ 道题花费了 $b_i$ 的时间，则最坏情况就是把 $b_i$ 也排序并一一对应。
于是问题变为：给定一个 $n$ 个点 $(i, a_i)$ 构成的右下阶梯，求一个 $n$ 个点 $(i, b_i)$ 构成的右下阶梯，使得有 $m$ 个 $i$ 满足 $a_i = b_i$。
$f_{i,j}$ 表示考虑前 $i$ 个点，$a_i = b_i$，且有 $j$ 个位置满足 $j < i, a_j = b_j$ 的最小代价。直接转移是 $O(Tn^2m)$ 的。使用斜率优化即可做到 $O(Tnm)$。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
//#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int N = 2005;
bool ST;
int n,m,a[N];
int g[N],f[N];
inline double cal(int i,int j){return 1.0*(g[i]-g[j])/(i-j);}//计算斜率
inline void dp(){
int st[N],tp;//单调栈
For(k,2,m){
swap(f,g);//将 f 数组和 g 数组交换
tp = 0;//栈清空
st[++tp] = k-1;//把上一位的数的位置加入栈中
For(i,k,n){
while(tp>1 && a[i] <= cal(st[tp], st[tp-1])) tp--;//如果此时a[i]的斜率小于栈顶的斜率，弹栈
int j = st[tp]; f[i] = g[j] + (i-j) * a[i];//更新答案
while(tp>1 && cal(i,st[tp]) <= cal(st[tp], st[tp-1])) tp--;//更新斜率，保证斜率单调递增
st[++tp] = i;//入栈
}
}
}
inline void solve(){
n = rd(), m = rd();
For(i,1,n) a[i] = rd();
sort(a+1,a+n+1,[](int x,int y){return x>y;});//从大到小排序
For(i,1,n) f[i] = i*a[i];//f[i] = 大于a[i]的数的个数 * a[i]的大小
//可以理解为如果要做到值为 a[i] 的题目， 就必须先学 f[i] 的时间
dp(),printf("%d\n", *min_element(f+m, f+n+1));
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("contest.in","r",stdin);
freopen("contest.out","w",stdout);
int T = rd(), Tim = clock();
while(T--) solve();
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
