【題目鏈接】: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;}新聞熱點
疑難解答
