原題：
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]));
}
