#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <unordered_map>
#include <memory.h>
#include <unordered_set>
#include <fstream>
#include <random>
using namespace std;
int h[301];
int dp[305][205][205];
int main(void)
{
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> h[i];
}
for(int i=0;i<=300;i++)
{
for (int j = 0; j <= 200; j++)
{
for (int k = 0; k <= 200; k++)
{
dp[i][j][k] = 1e9;
}
}
}
dp[0][0][0] = 0;
for (int i = 0; i < n + 2; i++)
{
for (int j = 0; j <= 200; j++)
{
for (int k = 0; k <= 200; k++)
{
if (dp[i][j][k] >= 1e9)
{
continue;
}
int a = j;
int b = k;
int c = h[i];
int m = min(a, min(b, c));
int cost = 7 * m + (a - m) * 3;
dp[i + 1][b - m][c - m] = min(dp[i + 1][b - m][c - m], dp[i][a][b] + cost);
int M = min(a - m, b - m);
int na = a - m - M;
int nb = b - m - M;
cost += (5 * M);
dp[i + 1][nb][c - m] = min(dp[i + 1][nb][c - m], dp[i][a][b] + cost + 3 * na);
m = min(a, b);
cost = 5 * m + (a - m) * 3;
dp[i + 1][b - m][c] = min(dp[i + 1][b - m][c], dp[i][a][b] + cost);
cost = 3 * a;
dp[i + 1][b][c] = min(dp[i + 1][b][c], dp[i][a][b] + cost);
}
}
}
int res = 1e9;
cout << dp[n + 2][0][0] << '\n';
return 0;
}
Compilation message
skyline.cpp: In function 'int main()':
skyline.cpp:88:6: warning: unused variable 'res' [-Wunused-variable]
88 | int res = 1e9;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
49732 KB |
Output is correct |
2 |
Correct |
27 ms |
49740 KB |
Output is correct |
3 |
Correct |
27 ms |
49720 KB |
Output is correct |
4 |
Correct |
30 ms |
49804 KB |
Output is correct |
5 |
Correct |
32 ms |
49784 KB |
Output is correct |
6 |
Incorrect |
27 ms |
49740 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |