UVA 11578 - Situp Benches(dp)
3583 단어 uva
제목 링크: 11578 - Situp Benches
제목: 건♂몸뚱이♂방에 두 개의 윗몸일으키기 방석이 있는데 각도를 조정할 때마다 10위안/10도, 매번 사용할 때마다 15위안이 든다. 지금은 n명의 시간 순서와 원하는 각도를 정하여 최소한의 비용을 요구한다.
사고방식: dp, dp[i][j][k]는 제i개인을 나타낸다. 한 각도는 j이고 또 하나는 k를 위한 최소 비용이다. 한 사람이 두 사람이 사용하는 상황과 분리해서 토론한 다음에 dp상태 이동 경로를 기록한다.이 출력 경로는 이 문제를 적지 않게 번거롭게 만들었다.그냥 슬기로운 거예요. 제가 얘를 할게요.♂나오다♂오다♂됐어.
코드:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define min(a,b) ((a)<(b)?(a):(b))
const int N = 10005;
int t, n, i, j, k, dp[N][5][5], ans, an[N];
struct Stu {
int t, l, id;
} s[N];
struct Out {
int n, l, r, out1, out2;
} out[N][5][5];
bool cmpt(Stu a, Stu b) {
return a.t < b.t;
}
bool cmpid(Stu a, Stu b) {
return a.id < b.id;
}
void print(int n, int l, int r) {
Out next = out[n][l][r];
if (n == 0) return;
if (next.out2 != -1) {
an[s[n - 1].id] = next.out1;
an[s[n].id] = next.out2;
}
else {
an[s[n].id] = next.out1;
}
print(next.n, next.l, next.r);
}
int main() {
scanf("%d", &t);
while (t--) {
ans = INF;
memset(dp, INF, sizeof(dp));
dp[0][0][0] = 0;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%d%d", &s[i].t, &s[i].l);
s[i].l = s[i].l / 10 - 1;
s[i].id = i;
}
sort(s + 1, s + n + 1, cmpt);
for (i = 1; i <= n; i++) {
int tmp1 = s[i].l;
if (i == n || s[i].t != s[i + 1].t) {
for (j = 0; j < 5; j++) {
for (k = 0; k < 5; k++) {
if (dp[i][tmp1][k] > dp[i - 1][j][k] + abs(tmp1 - j) * 10) {
dp[i][tmp1][k] = dp[i - 1][j][k] + abs(tmp1 - j) * 10;
out[i][tmp1][k].l = j; out[i][tmp1][k].r = k; out[i][tmp1][k].n = i - 1;
out[i][tmp1][k].out1 = 1; out[i][tmp1][k].out2 = -1;
}
if (dp[i][j][tmp1] > dp[i - 1][j][k] + abs(tmp1 - k) * 10) {
dp[i][j][tmp1] = dp[i - 1][j][k] + abs(tmp1 - k) * 10;
out[i][j][tmp1].l = j; out[i][j][tmp1].r = k; out[i][j][tmp1].n = i - 1;
out[i][j][tmp1].out1 = 2; out[i][j][tmp1].out2 = -1;
}
}
}
}
else {
int tmp2 = s[i + 1].l;
for (j = 0; j < 5; j++) {
for (k = 0; k < 5; k++) {
if (dp[i + 1][tmp1][tmp2] > dp[i - 1][j][k] + abs(tmp1 - j) * 10 + abs(tmp2 - k) * 10) {
dp[i + 1][tmp1][tmp2] = dp[i - 1][j][k] + abs(tmp1 - j) * 10 + abs(tmp2 - k) * 10;
out[i + 1][tmp1][tmp2].l = j; out[i + 1][tmp1][tmp2].r = k; out[i + 1][tmp1][tmp2].n = i - 1;
out[i + 1][tmp1][tmp2].out1 = 1; out[i + 1][tmp1][tmp2].out2 = 2;
}
if (dp[i + 1][tmp2][tmp1] > dp[i - 1][j][k] + abs(tmp2 - j) * 10 + abs(tmp1 - k) * 10) {
dp[i + 1][tmp2][tmp1] = dp[i - 1][j][k] + abs(tmp2 - j) * 10 + abs(tmp1 - k) * 10;
out[i + 1][tmp2][tmp1].l = j; out[i + 1][tmp2][tmp1].r = k; out[i + 1][tmp2][tmp1].n = i - 1;
out[i + 1][tmp2][tmp1].out1 = 2; out[i + 1][tmp2][tmp1].out2 = 1;
}
}
}
i++;
}
}
int lv, rv;
for (j = 0; j < 5; j++) {
for (k = 0; k < 5; k++) {
if (ans > dp[n][j][k] + j * 10 + k * 10) {
ans = dp[n][j][k] + j * 10 + k * 10;
lv = j; rv = k;
}
}
}
printf("%d
", ans + 15 * n);
print(n, lv, rv);
for (i = 1; i <= n; i++)
printf("%d
", an[i]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA - 10986 Sending email(Dijkstra 인접 테이블 + 우선 순위 대기열 최적화)제목 대의: s점에서 t점까지의 최소 거리를 구하는 그림을 주세요. 확인: 적나라한 최단길이지만 n이 너무 크면 인접 행렬을 사용할 수 없기 때문에 Dijkstra에 대한 인접표 + 우선 대기열 최적화가 필요합니다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.