input:homework.in output:homework.out

时间限制: 1000 ms 空间限制: 262144 KB

题目描述

输入

输出

样例输入

1
2
5 10
3 4 6 100 1

样例输出

1
60

数据范围限制


提示

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
#define int long long
#define rr register
int T,n,t[2005],sum[2005],f[2005];
int min(int a,int b)
{
if(a>b)
return b;
return a;
}
signed main()
{
freopen("homework.in","r",stdin);
freopen("homework.out","w",stdout);
scanf("%lld %lld",&n,&T);
memset(f,0x3f3f3f3f,sizeof f);
for(rr int i=1;i<=n;i++)
{
scanf("%lld",&t[i]);
sum[i]=sum[i-1]+t[i];
}
f[0]=0,f[1]=sum[1]+2*T;
for(rr int i=1;i<=n;i++)
for(rr int j=0;j<i;j++)
f[i]=min(f[i],f[j]+sum[i-j]+2*T);
printf("%lld",f[n]);
}