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();}新聞熱點
疑難解答
