Petrozavodsk Winter Camp, Day 8, 2014, Ship

$dp(i,j)$表示i~j这段还没运走时的状态,包括 运输了多少次,还剩多少空间

每次枚举运输左边还是右边转移

#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = int(j); i <= int(k); ++ i)
#define dwn(i, j, k) for (int i = int(j); i >= int(k); -- i)
using namespace std;
typedef pair<int, int> P;
const int N = 1e4 + ;
P dp[][N];
int w[N]; int main() {
int n, t;
scanf("%d%d", &t, &n);
rep(i, , n) scanf("%d", w + i); P tmp;
auto Enlarge = [&](P &a, P &b) {
if (a.first == -) a = b;
else {
if (a.first > b.first || (a.first == b.first && a.second < b.second)) a = b;
}
};
for (int i = ; i <= n; ++ i) dp[(n & )][i].first = -;
dp[(n & )][] = P(, );
dwn(l, n, ) { // i, j 之间还没消去
int cur = l & , next = cur ^ ;
// cout << l << ' ' << dp[cur][3].first << ' ' << dp[cur][3].second << '\n';
for (int i = ; i <= n; ++ i) dp[next][i].first = -;
for (int i = ; i + l - <= n; ++ i)
if (dp[cur][i].first != -) {
int j = i + l - ;
// 选第i个
if (w[i] <= dp[cur][i].second) {
tmp = P(dp[cur][i].first, dp[cur][i].second - w[i]);
Enlarge(dp[next][i + ], tmp);
}
else {
tmp = P(dp[cur][i].first + , t - w[i]);
Enlarge(dp[next][i + ], tmp);
}
// 选第jge
if (w[j] <= dp[cur][i].second) {
tmp = P(dp[cur][i].first, dp[cur][i].second - w[j]);
Enlarge(dp[next][i], tmp);
}
else {
tmp = P(dp[cur][i].first + , t - w[j]);
Enlarge(dp[next][i], tmp);
} }
}
// cout << dp[0][3].first << ' ' << dp[0][3].second << '\n';
int ans = ;
for (int i = ; i <= n; ++ i)
if (dp[][i].first != -)
ans = min(ans, dp[][i].first);
printf("%d\n", ans); }
/*
4 5
1 1 3 1 2
*/
上一篇:[精讲]15-Winodws Server 2012 工作文件夹


下一篇:PKCS RSA执行标准