神贪心。。。
b[i]=a[1]-(n-1)*d;
每次找价值最大的k
使b[k]~b[n]都++
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using
namespace std;#define maxn 6000 #define ll long longinline
long long min(long long x, long long y) {return
x<y?x:y;};inline
long long max(long long x, long long y) {return
x>y?x:y;}; inline
long long ABS(long long x) {return
x<0?-x:x;};ll a[maxn];ll b[maxn];int n;ll now=0,pp,maxx=-0x3fffffffffffffLL,jj,up=0x3fffffffffffffLL;ll d,ans;int m,i;int main(){ scanf("%d",&m); while(m--){ scanf("%d%lld",&n,&d); for(i=1;i<=n;i++)scanf("%lld",&a[i]); b[1]=a[1]; for(i=2;i<=n;i++)b[i]=b[i-1]-d; if(a[1]+(n-1)*d<a[n]||a[n]<a[1]-(n-1)*d){ printf("impossible\n"); }else{ ans=0; for(;a[n]!=b[n];){ int
j; now=0,maxx=-0x3ffffffffffffffLL,jj=0,up=0x3fffffffffffffLL; for( j=n;j>=2;j--){ if(b[j]>=a[j])now--; else
now++,up=min(up,a[j]-b[j]); if(now>maxx&&b[j]<b[j-1]+d){ maxx=now; jj=j; pp=up; } } pp=min(pp,b[jj-1]+d-b[jj]); for(j=jj;j<=n;j++)b[j]+=pp; } for(i=1;i<=n;i++)ans+=ABS(b[i]-a[i]); printf("%lld\n",ans); } } } |
bzoj1484: [HNOI2009]通往城堡之路,布布扣,bubuko.com
原文：http://www.cnblogs.com/wangyucheng/p/3636867.html