CF990 E Post Lamps
[ 原题链接 ] http://codeforces.com/contest/990/problem/E
不同的区间长度 $$i$$ 的价格不同、需要的区间个数也不同，不满足二分或三分的特性，因此需要枚举 $$i$$。
在确定 $$i$$ 以后，pos 从 0 开始划分区间，区间必须覆盖 0 ~ n 的所有段（可以重复放）。
如果遇到 pos 不可以放灯，那么 pos 往回走到第一个可以放灯的位置。$$O(n)$$ 预处理上一个可以放灯的位置。
直到 pos 走到 n，或者遇到 pos+1 ~ pos+$$ i $$ 均不可放灯的情况，这样尽量往后放、少放灯的贪心是最优的。
而当 $$i$$ 小于最长连续一段不可放灯的长度时，最长的那段是无法覆盖全的。
因此进一步缩小了 $$i$$ 的枚举范围，经测试时限 $$4.5s$$ 可以 AC。
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
char ch=getchar(); int f=1; t=0;
while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int maxn=1000010;
int n,m,k,mx,cnt[maxn];
bool d[maxn];
ll s[maxn],ans=1LL<<60;
int main() {
read(n); read(m); read(k);
for (int i=1;i<=m;i++) {
int x; read(x);
d[x]=1;
}
if (d[0]) { printf("-1\n"); return 0; }
for (int i=0;i<n;i++) {
if (!d[i]) continue;
cnt[i]=1; if (i) cnt[i]+=cnt[i-1];
mx=max(mx,cnt[i]);
}
for (int i=1;i<=k;i++) read(s[i]);
for (int i=mx;i<=k;i++) {
int pos=0,cntcnt=0;
while (pos<n) {
if (d[pos]) {
if (cnt[pos]==i) break;
pos-=cnt[pos];
} else {
cntcnt++;
pos+=i;
}
}
if (pos>=n) ans=min(ans,s[i]*cntcnt);
}
if (ans>=1LL<<60) ans=-1;
printf("%I64d\n",ans);
return 0;
}
