原題:
http://172.16.0.132/senior/#contest/show/2055/2
題目描述:
我們需要將一個文件復制到n個服務器上,這些服務器的編號為S1, S2, …, Sn。
首先掺出,我們可以選擇一些服務器翎承,直接把文件復制到它們中;將文件復制到服務器Si上,需要花費ci > 0的置放費用豁陆。對于沒有直接被復制文件的服務器Si來說篇裁,它依次向后檢查Si+1, Si+2, …直到找到一臺服務器Sj:Sj中的文件是通過直接復制得到的沛慢,于是Si從Sj處間接復制得到該文件,這種復制方式的讀取費用是j – i(注意j>i)达布。另外团甲,Sn中的文件必須是通過直接復制得到的,因為它不可能間接的通過別的服務器進行復制黍聂。我們設計一種復制方案躺苦,即對每一臺服務器確定它是通過直接還是間接的方式進行復制(Sn只能通過直接方式),最終使每一臺服務器都得到文件产还,且總花費最小匹厘。
輸入:
輸入文件的第一行有一個整數(shù)n,表示服務器的數(shù)目脐区。輸入文件的第二行有n個整數(shù)愈诚,順數(shù)第i個表示ci:在Si上直接復制文件的費用
輸出:
輸出文件中只包含一個整數(shù),即最少需要花費的費用牛隅。
樣例輸入:
10
2 3 1 5 4 5 6 3 1 2
樣例輸出:
18
數(shù)據(jù)范圍限制:
60%的數(shù)據(jù)中炕柔,1 <= n <= 1 000
100%的數(shù)據(jù)中,1 <= n <= 1 000 000
80%的數(shù)據(jù)中倔叼, 1 <= ci <= 50
100%的數(shù)據(jù)中汗唱,1 <= ci <= 1 000 000 000
最終結(jié)果可能較大,請注意選擇適當?shù)臄?shù)據(jù)類型進行計算丈攒。
提示:
分析:
dp
設f[i,0]表示第i個機器直接復制哩罪,f[i,1]表示第i個機器間接復制授霸,
f[n,0]=c[n];
很明顯,轉(zhuǎn)移方程為:
f[i,0]=min(f[i+1,0],f[i+1,1])+c[i];
f[i,1]=min(f[i,1],f[j,1]+(j-i-1)*(j-i)/2);
然后用隊列優(yōu)化即可
實現(xiàn):
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,i,j;
long long ans,f[1000001][2],s[1000001],t[1000001],c[1000001];
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&c[i]);
memset(f,127,sizeof(f));
f[n][0]=c[n];
s[++s[0]]=f[n][0];
t[s[0]]=n;
for(i=n-1;i;i--)
{
f[i][0]=min(f[i+1][0],f[i+1][1])+c[i];
for(j=s[0];j;j--)
{
ans=(t[j]-i+1)*(t[j]-i)/2;
if(ans>=f[i][1]) break;
f[i][1]=min(f[i][1],s[j]+ans);
}
while(s[s[0]]>=f[i][0] && s[0]) s[0]--;
s[++s[0]]=f[i][0];
t[s[0]]=i;
}
printf("%lld",min(f[1][1],f[1][0]));
}