地址 http://poj.org/problem?id=3709
n 个数, 可进行把一个数减小的操作, 代价为减小的值. 现求使数列任意一个数都存在至少 k-1 个数和他相同, 问操作的最小代价.
可以先考虑最小的数, 由于只能减, 所以必须得至少 k-1 个数减为最小数, 贪心策略: 从小到大从最小数开始的后面至少 k-1 个数必须减为他自己这一块代价才最小. 很好想, 如果里面有一个不选, 那必须有一个更大的数下降, 并且不选的这个数在之后也使后面另一块的数减的更多, 所以总是把连续的至少 k 个数减为开头最小的那个数. 那就是数列上划分块的 dp,$f[i]$ 是到 $i$ 时最小代价.
$f[i]=min{f[j]+sum[i]-sum[j]-(i-j)*a[j+1]} 0<=j<=i-k 且 j[1,k-1]$
然后拆开就是一个常规的斜率优化了. 注意一下开头 k-1 个是不能作为决策点的 (因为无解), 不要进队. 0 是可以进队的.
没了.
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- using namespace std;
- typedef long long ll;
- template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;}
- template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;}
- template<typename T>inline T _min(T A,T B){return A<B?A:B;}
- template<typename T>inline T _max(T A,T B){return A>B?A:B;}
- template<typename T>inline T read(T&x){
- x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
- while(isdigit(c))x=x*10+c-'0',c=getchar();return f?x=-x:x;
- }
- const int N=500000+7;
- ll f[N],sum[N];
- int a[N],q[N],T,n,k,l,r;
- inline ll x(int j){return (ll)a[j+1];}
- inline ll y(int j){return f[j]+j*1ll*a[j+1]-sum[j];}
- int main(){//freopen("test.in","r",stdin);//freopen("tmp.out","w",stdout);
- read(T);while(T--){
- read(n),read(k);l=1,r=0;
- for(register int i=1;i<=n;++i)sum[i]=read(a[i])+sum[i-1];
- for(register int i=k;i<=n;++i){
- if(i==k||i>=(k<<1)){
- while(l<r&&(y(i-k)-y(q[r]))*(x(q[r])-x(q[r-1]))<=(y(q[r])-y(q[r-1]))*(x(i-k)-x(q[r])))--r;
- q[++r]=i-k;
- }
- while(l<r&&y(q[l+1])-y(q[l])<=1ll*i*(x(q[l+1])-x(q[l])))++l;
- f[i]=f[q[l]]+sum[i]-sum[q[l]]-(i-q[l])*1ll*a[q[l]+1];
- }
- printf("%lld\n",f[n]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2974006.html