5月5日 · 2018年

# 整齐打印

for (int i = 1; i <= n; i++) {
for (int k = 1; k <= i; k++)
dp[i] = std::min(dp[i], dp[k - 1] + extraSpaces(k, i));


1~k-1这一段的空格数就是dp[k-1]

k~i这段的就是通过extraSpaces()函数计算的

int ret = M - end + begin;
for (int k = begin; k <= end; ++k) ret -= l[k]; // 根据公式计算空格数
if (ret < 0) return POSITIVE_INFINITY; // 如果放不下，那么就是不合法的组合
if (end == n) return 0; // 最后一行不计入
return ret * ret * ret;


long long保平安

for (int k = 1; k <= i; k++)  dp[i] = std::min(dp[i], dp[k - 1] + extraSpaces(k, i));


for (int i = 1; i <= n; i++) {
for (int k = i; k >= 1; k--) {
long long v = extraSpaces(k, i);
if (v == POSITIVE_INFINITY) break;
dp[i] = std::min(dp[i], dp[k - 1] + v);
}
}


void calc() {
for (int from = 1; from <= n; from++) {
extraSpacesMESCH[from][from] = M - l[from];
for (int to = from + 1; to <= n; to++) {
extraSpacesMESCH[from][to] = extraSpacesMESCH[from][to - 1] - l[to] - 1;
}
}
}

long long extraSpaces(int begin, int end) {
long long ret = extraSpacesMESCH[begin][end];
if (ret < 0) return POSITIVE_INFINITY;
if (end == n) return 0;
return ret * ret * ret;
}


#include <bits/stdc++.h>

#define MAX_N 10007
#define POSITIVE_INFINITY  0x3F3F3F3F3F3F3F3F

int n, M;
int l[MAX_N] = {0};
int extraSpacesMESCH[MAX_N][MAX_N] = {0};
long long dp[MAX_N] = {0};

long long extraSpaces(int begin, int end) {
//    long long ret = M - end + begin;
//    for (int k = begin; k <= end; ++k) ret -= l[k];
long long ret = extraSpacesMESCH[begin][end];
if (ret < 0) return POSITIVE_INFINITY;
if (end == n) return 0;
return ret * ret * ret;
}

void calc() {
for (int from = 1; from <= n; from++) {
extraSpacesMESCH[from][from] = M - l[from];
for (int to = from + 1; to <= n; to++) {
extraSpacesMESCH[from][to] = extraSpacesMESCH[from][to - 1] - l[to] - 1;
}
}
}

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif

scanf("%d%d", &n, &M);
for (int i = 1; i <= n; ++i)
scanf("%d", &l[i]);
for (int i = 1; i <= n; ++i)
dp[i] = POSITIVE_INFINITY;
dp[0] = 0;
calc();
for (int i = 1; i <= n; i++) {
for (int k = i; k >= 1; k--) {
//            dp[i] = std::min(dp[i], dp[k - 1] + extraSpaces(k, i));
long long v = extraSpaces(k, i);
if (v == POSITIVE_INFINITY) break;
dp[i] = std::min(dp[i], dp[k - 1] + v);
}
}
printf("%lld\n", dp[n]);
}


0 条回应