http://www.lydsy.com/JudgeOnline/PRoblem.php?id=1010 Description P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1…N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第j个玩具放到一个容器中，那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过L。但他希望费用最小. Input 第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7 Output 输出最小费用 Sample Input 5 4 3 4 2 1 4 Sample Output 1
先列出n^2的dp： dp[i]=min(dp[j]+(sum[i]-sum[j]+i-j-1-L)^2) (j < i) 然后设循环中的k是最右解，j是普通解，列出不等式，化简成一侧是f【i】的，左侧是/的形式： (dp[k]+(f[k]+c)^2-dp[j]-(f[j]+c)^2)/2*(f[k]-f[j])<=f[i] 每个点是( （dp[k]+(f[k]+c)^2）, 2*f[k] )
本来是把正常小于i的所有j循环,找最大的k…然后现在为了快点找k 所以推出这个关系, 对于所有j和那个点连起来斜率都小于等于f[i]的就是k,于是用f[i]去找最右下的点。 显然如果出现上凸的，用f[i]平移的话，最后一定不会是这个点，就没用了。所以就是个下凸的凸包。。。维护上面的点即可，还是个单调队列，不用二分找这个点，因为对于当前i满足这个式子的k和j对于i+1。。。f[i+1]>f[i]。所以一定还满足这个式子。。。就是个单调队列了=。=从头找，不合法的对后面的答案没有用了，就删掉（head++），找到第一个就一定是这个点，因为考虑图形是斜率逐渐增大的，第一个找到的点就是最右下的！
#include <cstdio>#include <iostream>#include <cstring>typedef long long LL;using namespace std;int n;const int nn=51000;LL l,c[nn],L;LL dp[nn];LL sum[nn];struct pll{ long long first,second; int pos;} stak[nn],tmp;int head,last;int cross(pll a,pll b,pll c){ return (b.first-a.first)*(c.second-a.second)-(c.first-a.first)*(b.second-a.second) > 0;}LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}void add(LL x,LL y,int i){ // cout <<"x = "<<x <<" y = "<<y<<endl; while(last > head){ tmp.first = x,tmp.second = y,tmp.pos = i; if(cross(stak[last-1],stak[last],tmp)) break; last--; } stak[++last].first = x; stak[last].second = y; stak[last].pos = i; // cout << stak[last].first <<" "<<stak[last].second<<endl;}void init(){// scanf("%d",&n);// cin>>l;// l++;// for(int i = 1 ;i <= n;i++){// cin>>c[i];//scanf("%I64d",&c[i]);// sum[i]=sum[i-1]+c[i];// }// for(int i = 1; i <= n ; i++)// sum[i] += i; n=read();L=read();l=L+1; for(int i=1;i<=n;i++)c[i]=read(); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+c[i]; for(int i=1;i<=n;i++)sum[i]+=i;}double sp(pll k,pll j){ // cout <<" "<<(j.first-k.first)<<endl; return (j.second-k.second)/(j.first-k.first);}double check(int j,int k){ return (dp[k]+(sum[k]+l)*(sum[k]+l)-dp[j]-(sum[j]+l)*(sum[j]+l))/(2.0*(sum[k]-sum[j]));}void sov(){ dp[0]=0; head = 1; last = 1; stak[1].first = stak[1].second = stak[1].pos = 0; for(int i=1;i<=n;i++){ // cout <<i <<endl; while(head < last && check(stak[head].pos,stak[head+1].pos)<=sum[i]) head++; int t = stak[head].pos; // cout<<"t = "<<t<<endl; // printf("sum[%d] = %I64d sum[%d] = %I64d /n",i,sum[i],t,sum[t]); dp[i] = dp[t]+(sum[i]-sum[t]-l)*(sum[i]-sum[t]-l); // cout<<"dp = "<<dp[i]<<endl; // add(2*sum[i],dp[i]+(sum[i]+l)*(sum[i]+l),i); tmp.first = 2*sum[i];tmp.second = dp[i]+(sum[i]+l)*(sum[i]+l);tmp.pos = i; while(head < last && check(stak[last].pos,tmp.pos)< check(stak[last-1].pos,stak[last].pos))last--; stak[++last]=tmp; // cout <<"y = "<<dp[i]+(sum[i]+l)*(sum[i]+l) << " x = "<<2*sum[i]<<endl; }// for(int i = 1; i <= n ; i++)// printf("dp[%d] = %I64d/n",i,dp[i]); cout<<dp[n]<<endl;//printf("%I64d/n",dp[n]);}int main(){ init(); sov(); return 0;}特别行动队。 http://www.lydsy.com/JudgeOnline/problem.php?id=1911 上凸包，其实可以直接判断等式，而不用叉乘判断凸包，都一样。
#include <cstdio>#include <iostream>#include <cstring>using namespace std;int n,A,B,C,head,last;const int maxn = 1e6+10;long long a[maxn],sum[maxn],f[maxn],q[maxn];void init(){ scanf("%d",&n); scanf("%d%d%d",&A,&B,&C); for(int i = 1; i <= n ; i++){ scanf("%lld",&a[i]); sum[i] = sum[i-1]+a[i]; }}double check(int j,int k){ return (double)(f[k]-f[j]+A*((sum[k]*sum[k])-(sum[j]*sum[j]))+B*(sum[j]-sum[k]))/(2.0*(sum[k]-sum[j])*A);}void sov(){ head = last = 1;q[1] = 0; for(int i = 1; i <= n ; i++){ while(head < last && check(q[head],q[head+1]) <= sum[i]) head++; f[i] = f[q[head]]+A*(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])+B*(sum[i]-sum[q[head]])+C; while(head < last&& check(q[last-1],q[last]) > check(q[last],i)) last--; q[++last] = i; } printf("%lld/n",f[n]);}int main(){ init(); sov();}新闻热点
疑难解答
