Codeforces 983C Elevator dp (看题解)

Elevator

怎么今天写啥题都不会写啊, 我是傻了吗。。

把电梯里面四个人的目标点当作状态, 然后暴力转移。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); int dp[][][][][][];
int n, a[N], b[N];
int cur = , lst = ; inline bool chkmin(int &a, int b) {
return a > b ? a = b, true : false;
} int main() {
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
memset(dp[cur], inf, sizeof(dp[cur]));
dp[cur][][][][][] = * n;
for(int i = ; i <= n; i++) {
swap(cur, lst);
memset(dp[cur], inf, sizeof(dp[cur]));
for(int c1 = ; c1 >= ; c1--) {
for(int c2 = ; c2 >= ; c2--) {
for(int c3 = ; c3 >= ; c3--) {
for(int c4 = ; c4 >= ; c4--) {
for(int f = ; f <= ; f++) {
int& ret = dp[lst][f][c1][c2][c3][c4];
if(ret >= inf) continue;
if(!c1 && i < n) {
chkmin(dp[cur][a[i + ]][b[i + ]][c2][c3][c4], ret + abs(f - a[i + ]));
} else if(c1) {
chkmin(dp[lst][c1][][c2][c3][c4], ret + abs(f - c1));
}
if(!c2 && i < n) {
chkmin(dp[cur][a[i + ]][c1][b[i + ]][c3][c4], ret + abs(f - a[i + ]));
} else if(c2) {
chkmin(dp[lst][c2][c1][][c3][c4], ret + abs(f - c2));
}
if(!c3 && i < n) {
chkmin(dp[cur][a[i + ]][c1][c2][b[i + ]][c4], ret + abs(f - a[i + ]));
} else if(c3) {
chkmin(dp[lst][c3][c1][c2][][c4], ret + abs(f - c3));
}
if(!c4 && i < n) {
chkmin(dp[cur][a[i + ]][c1][c2][c3][b[i + ]], ret + abs(f - a[i + ]));
} else if(c4) {
chkmin(dp[lst][c4][c1][c2][c3][], ret + abs(f - c4));
}
}
}
}
}
}
}
int ans = inf;
for(int i = ; i <= ; i++)
ans = min(ans, dp[lst][i][][][][]);
printf("%d\n", ans);
return ;
} /*
*/
上一篇:connot connect to mysql 10061


下一篇:103 保序回归 isotonic regression