【Codeforces 797F】Mice and Holes

相关链接

题目传送门：http://codeforces.com/contest/797/problem/F

解题报告

这题我是用的一个非常鬼畜的背包DP过的，时间复杂度：$O(n^2 \log n)$
看提交记录的话，似乎可以用很多种方法做到$O(n^2)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5009;
const LL INF = 1e15;

int n,m,sum,x[N];
LL f[N],tmp,cost[N];
pair<int,int> mdy[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read(); m = read();
	for (int i=1;i<=n;i++) x[i] = read(), f[i] = INF;
	for (int i=1;i<=m;i++) mdy[i].first = read(), sum += (mdy[i].second = read());
	if (sum < n) puts("-1"), exit(0);
	sort(x+1, x+1+n); sort(mdy+1, mdy+1+m);
	for (int j=1,tot,pos;tot=mdy[j].second,pos=mdy[j].first,j<=m;j++) {
		for (int i=1;i<=n;i++) cost[i] = abs(x[i] - pos) + cost[i-1];
		for (int len=1;len=min(len,tot),tot>0;tot-=len,len<<=1) {
			for (int l=n-len+1,r=n;l>0;--l,--r) {
				f[r] = min(f[r], cost[r] - cost[l-1] + f[l-1]);
			} 
		}
	}
	printf("%lld\n",f[n]);
	return 0;
}