【贪心】AGC027B Garbage Collector_综合

分析：

考场上不知道怎么就想错了。。。

想了一个错误的DP，然而当时并没有发现。。。然后就挂了。。。

其实正解和我的DP差不多刚好反着来（能过那么多数据真是奇迹），我的DP求出来的几乎是一个最劣解。

不扯那么多了，其实想清楚还是很简单的一题：
很显然，假设机器人总共丢了 $k$ 次垃圾，那么丢垃圾的代价已经固定了（N*x+k*x），现在就是要求消耗在路途中的代价。

其实通过那个错误的DP也能发现这个特征：
每一次丢垃圾，路途中的代价可以表示为：
$……9*pos_a+7*pos_b + 5*pos_c+5*pos_d$
其中 $(……< a< b< c< d)$

观察这个式子，发现每一次扔垃圾，代价总是最远的两个点*5+第三远的点*7+……

那么一个很直观的贪心思路就是：最远的k的点都*5，次远的k个点都*5，再次远的k个点*7，……

所以可以枚举K，然后每次算最远的K的点的和，次远的K个点的和……，这个可以借助前缀和O(1)区间求和。时间复杂度又是调和级数。。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 200010
using namespace std;
typedef long long ll;
ll a[MAXN],x,pre[MAXN],ans;
int n;
int main(){SF("%d%lld",&n,&x);for(int i=1;i<=n;i++){SF("%lld",&a[i]);pre[i]=pre[i-1]+a[i];ans+=a[i]*5ll+2ll*x;}for(int k=1;k<n;k++){ll res=k*x;for(int j=n,cnt=1;j>0;cnt++){int j1=max(0,j-k);ll sum=pre[j]-pre[j1];res+=max(5ll,cnt*2ll+1ll)*sum;if(res>ans)break;j=j1;}ans=min(ans,res);}PF("%lld",ans+1ll*n*x);}