原题：
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只能通过直接方式），最终使每一台服务器都得到文件，且总花费最小。
输入：
输入文件的第一行有一个整数n，表示服务器的数目。输入文件的第二行有n个整数，顺数第i个表示ci：在Si上直接复制文件的费用
输出：
输出文件中只包含一个整数，即最少需要花费的费用。
样例输入：
10
2 3 1 5 4 5 6 3 1 2
样例输出：
18
数据范围限制：
60%的数据中，1 <= n <= 1 000
100%的数据中，1 <= n <= 1 000 000
80%的数据中， 1 <= ci <= 50
100%的数据中，1 <= ci <= 1 000 000 000
最终结果可能较大，请注意选择适当的数据类型进行计算。
提示：
分析：
dp
设f[i,0]表示第i个机器直接复制，f[i,1]表示第i个机器间接复制，
f[n,0]=c[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);
然后用队列优化即可
实现：
#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]));
}
