洛谷 P1934 封印

题目传送门

解题思路:

f[i]表示打到第i层的最小值

AC代码:

#include<iostream>
#include<cstdio>

using namespace std;

long long n,t,a[1001],sum[1001];
long long f[1001];

inline long long min(long long s,long long d) {
    if(s > d) return d;
    return s;
}

int main() {
    scanf("%d%d",&n,&t);
    for(int i = 1;i <= n; i++) {
        scanf("%d",&a[i]);
        sum[i] = sum[i-1] + a[i];
    }
    for(int i = 1;i <= n; i++) {
        f[i] = a[i] * n * n + f[i-1];
        for(int j = i - 1;j >= 1; j--)
            if(a[i] + a[j] <= t)
                f[i] = min(f[i],f[j-1] + (a[j] + a[i]) * (sum[i] - sum[j-1]));
    }
    printf("%lld",f[n]);
    return 0;
}