이산화 dp
4648 단어 ACM_동적 기획
/**********************jibancanyang**************************
*Author :jibancanyang
*Created Time : 4/ 8 22:12:57 2016
*File Name : poj3666.cpp
* : dp
* : dp, , .
***********************[email protected]**********************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
vector<int> vi;
#define xx first
#define yy second
#define sa(n) scanf("%d", &(n))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define vep(c) for(decltype((c).begin() ) it = (c).begin(); it != (c).end(); it++)
const int mod = int(1e9) + 7, INF = 0x3fffffff, maxn = 2e3 + 12;
ll dp[maxn][maxn], a[maxn], b[maxn];
ll abss(ll x) {
return x < 0 ? -x : x;
}
int main(void)
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
cin.sync_with_stdio(false);
int n;
while (cin >> n) {
rep (i, 0, n) cin >> a[i], b[i] = a[i];
sort(b, b + n);
rep (i, 0, n) dp[0][i] = abss(b[i] - a[0]);
ll ans = ll(1e18);
for (int i = 1; i < n; i++) {
ll last = ll(1e18);
for (int j = 0; j < n; j++) {
last = min(last, dp[i - 1][j]);
dp[i][j] = last + abss(a[i] - b[j]);
if (i == n - 1) ans = min(ans, dp[i][j]);
}
}
cout << (n == 1 ? 0 : ans) << endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA 1025_A Spy in the Metro[제의] (소자서) 한 사람이 플랫폼 1에서 출발하면 차를 타려면 시간 T에 플랫폼 n에 도착해야 한다. 플랫폼에서 차를 기다리는 시간이 가장 짧기 때문에 그녀는 두 방향의 열차를 타고 버스가 정차할 때 갈아타야 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.