【BZOJ 1010】[HNOI2008]玩具装箱toy

2019-11-08 03:05:42

字体：大中小

来源：转载

供稿：网友

【题目链接】:http://www.lydsy.com/JudgeOnline/PRoblem.php?id=1010

【题意】

【题解】 dp[i] = min(dp[i],dp[j]+sqr(sum[i]-sum[j]+i-(j+1)-l)); dp[i] = min(dp[i],dp[j]+sqr((sum[i]+i)-(sum[j]+j)-(l+1))); 令f[i] = sum[i] + i; 令c=l+1; dp[i] = min(dp[i],dp[j]+sqr(f[i]-f[j]-c)); 当j< k< i时; 假设 dp[j]+sqr(f[i]-f[j]-c)>dp[k]+sqr(f[i]-f[k]-c) ······① 设i之后的状态t; f[t]=f[i]+v; 想知道i对后面的t的状态的影响; dp[j]+sqr(f[t]-f[j]-c)>dp[k]+sqr(f[t]-f[k]-c); dp[j]+sqr(f[i]+v-f[j]-c)>dp[k]+sqr(f[i]+v-f[k]-c); dp[j]+sqr(f[i]-f[j]-c)+sqr(v)+2*(f[i]-f[j]-c)v>dp[k]+sqr(f[i]-f[k]-c)+sqr(v)+2(f[i]-f[k]-c)*v; f[i]-f[j]-c>f[i]-f[k]-c -> f[k]>f[j]; 而f[k]>f[j]显然成立(k>j,且f单调递增); 所以,当j< k< i,①式成立的时候只要考虑决策点k就好;j不会对后面的答案造成影响;不用考虑它; 然后看看①式成立的条件是什么; ->将①式展开; dp[j]+sqr(f[i]-f[j]-c)>dp[k]+sqr(f[i]-f[k]-c) dp[j]+sqr(f[i])+sqr(f[j]+c)-2*f[i](f[j]+c)>dp[k]+sqr(f[i]+sqr(f[k]+c)-2*f[i](f[k]+c); dp[j]+sqr(f[j]+c)-2*f[i](f[j]+c)>dp[k]+sqr(f[k]+c)-2*f[i](f[k]+c); dp[j]-dp[k]+sqr(f[j]+c)-sqr(f[k]+c)>2*f[i](f[j]+c)-2*f[i](f[k]+c); (dp[j]-dp[k]+sqr(f[j]+c)-sqr(f[k]+c))>2*fi f[j]>f[k]要改变不等式方向 (dp[j]-dp[k]+sqr(f[j]+c)-sqr(f[k]+c))/(2*(f[j]-f[k]))< f[i] ····② 也就是说,如果②式成立的话; 就k的决策更好,否则的话j的决策更好; 且根据上面的分析可知,这时候的决策对后面的结果不会有“坏”的影响; (也就是当前的决策时可以推出后面的答案的); 写个单调队列就好;

【完整代码】

/************************************************************** Problem: 1010 User: chengchunyang Language: C++ Result: Accepted Time:176 ms Memory:3052 kb****************************************************************/#include <bits/stdc++.h>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%lld",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int N = 5e4+100;LL n,l,C;LL c[N],f[N],sum[N],dp[N];int dl[N],h,t;LL sqr(LL x) { return x*x;}double ju(int j,int k){ double t = (dp[j]-dp[k]+sqr(f[j]+C)-sqr(f[k]+C))/(2*(f[j]-f[k])); return t;}int main(){ //freopen("F://rush.txt","r",stdin); rel(n),rel(l);C = l+1; rep1(i,1,n) { rel(c[i]); sum[i] = sum[i-1]+c[i]; f[i] = sum[i]+i; } h = 1,t = 1; dl[1] = 0,dp[0] = 0; rep1(i,1,n) { while (h<t && ju(dl[h],dl[h+1])<=f[i]) h++; int temp = dl[h]; dp[i] = dp[temp] + sqr(f[i]-f[temp]-C); while (h<t && ju(dl[t-1],dl[t])>ju(dl[t-1],i)) t--; t++; dl[t] = i; } printf("%lld/n",dp[n]); return 0;}

上一篇：c语言之单链表

下一篇：eclipse快捷键的使用