http://www.lydsy.com/JudgeOnline/PRoblem.php?id=1010 Description P教授要去看奧運(yùn)，但是他舍不下他的玩具，于是他決定把所有的玩具運(yùn)到北京。他使用自己的壓縮器進(jìn)行壓縮，其可以將任意物品變成一堆，再放到一種特殊的一維容器中。P教授有編號(hào)為1…N的N件玩具，第i件玩具經(jīng)過(guò)壓縮后變成一維長(zhǎng)度為Ci.為了方便整理，P教授要求在一個(gè)一維容器中的玩具編號(hào)是連續(xù)的。同時(shí)如果一個(gè)一維容器中有多個(gè)玩具，那么兩件玩具之間要加入一個(gè)單位長(zhǎng)度的填充物，形式地說(shuō)如果將第i件玩具到第j個(gè)玩具放到一個(gè)容器中，那么容器的長(zhǎng)度將為 x=j-i+Sigma(Ck) i<=K<=j 制作容器的費(fèi)用與容器的長(zhǎng)度有關(guān)，根據(jù)教授研究，如果容器長(zhǎng)度為x,其制作費(fèi)用為(X-L)^2.其中L是一個(gè)常量。P教授不關(guān)心容器的數(shù)目，他可以制作出任意長(zhǎng)度的容器，甚至超過(guò)L。但他希望費(fèi)用最小. Input 第一行輸入兩個(gè)整數(shù)N，L.接下來(lái)N行輸入Ci.1<=N<=50000,1<=L,Ci<=10^7 Output 輸出最小費(fèi)用 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) 然后設(shè)循環(huán)中的k是最右解，j是普通解，列出不等式，化簡(jiǎn)成一側(cè)是f【i】的，左側(cè)是/的形式： (dp[k]+(f[k]+c)^2-dp[j]-(f[j]+c)^2)/2*(f[k]-f[j])<=f[i] 每個(gè)點(diǎn)是( （dp[k]+(f[k]+c)^2）, 2*f[k] )
本來(lái)是把正常小于i的所有j循環(huán),找最大的k…然后現(xiàn)在為了快點(diǎn)找k 所以推出這個(gè)關(guān)系, 對(duì)于所有j和那個(gè)點(diǎn)連起來(lái)斜率都小于等于f[i]的就是k,于是用f[i]去找最右下的點(diǎn)。 顯然如果出現(xiàn)上凸的，用f[i]平移的話，最后一定不會(huì)是這個(gè)點(diǎn)，就沒(méi)用了。所以就是個(gè)下凸的凸包。。。維護(hù)上面的點(diǎn)即可，還是個(gè)單調(diào)隊(duì)列，不用二分找這個(gè)點(diǎn)，因?yàn)閷?duì)于當(dāng)前i滿足這個(gè)式子的k和j對(duì)于i+1。。。f[i+1]>f[i]。所以一定還滿足這個(gè)式子。。。就是個(gè)單調(diào)隊(duì)列了=。=從頭找，不合法的對(duì)后面的答案沒(méi)有用了，就刪掉（head++），找到第一個(gè)就一定是這個(gè)點(diǎn)，因?yàn)榭紤]圖形是斜率逐漸增大的，第一個(gè)找到的點(diǎn)就是最右下的！
#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;}特別行動(dòng)隊(duì)。 http://www.lydsy.com/JudgeOnline/problem.php?id=1911 上凸包，其實(shí)可以直接判斷等式，而不用叉乘判斷凸包，都一樣。
#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();}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
