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