# AtCoder Beginner Contest 175 题解

# Problem D - Moving Piece (opens new window)

# 题目描述

$N$$N\leq5000$）个方格，从第$i$个方格会跳到第$P_i$个方格。$P$$1,\cdots,N$的一个排列。

# 题解

• $K\leq C$，此时我们应该选择前$K$个前缀和中的最大值。
• $K>C$，令$K=nc+r$，则我们可以选择
• 不循环，选择所有前缀和中的最大值。
• 循环$n$次，再加上前$r$个前缀和中的最大值。
• 循环$n-1$次，再加上所有前缀和中的最大值。

#include <climits>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

int main() {
int n, k;
cin >> n >> k;
vector<int> p(n), c(n);
for (int i = 0; i < n; ++i)
cin >> p[i];
for (int i = 0; i < n; ++i)
cin >> c[i];
ll ans = LLONG_MIN;
for (int i = 0; i < n; ++i) {
vector<bool> vis(n);
int idx = i;
vector<ll> sum = {0}, hi = {LLONG_MIN};
while (!vis[p[idx] - 1]) {
idx = p[idx] - 1;
vis[idx] = true;
sum.emplace_back(sum.back() + c[idx]);
hi.emplace_back(max(hi.back(), sum.back()));
}
int m = sum.size() - 1;
int f = k / m, rem = k % m;
ll result;
if (f > 0)
result = max(hi[m], max(sum[m] * f + (rem == 0 ? 0 : hi[rem]),
sum[m] * (f - 1) + hi[m]));
else
result = hi[rem];
ans = max(ans, result);
}
cout << ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <cmath>
#include <iostream>
#include <vector>

#define MAXN 5005
#define K 15

using namespace std;
typedef long long ll;
const ll LO = -1e16;
int n, k;

ll st[MAXN * 2][K];

ll query(int l, int r) {
int len = r - l + 1;
int j = log2(len);
return min(st[l][j], st[r - (1 << j) + 1][j]);
}

ll solve(vector<int> &v) {
int len = v.size();
vector<ll> s = {0};
for (int i = 0; i < 2 * len; ++i)
s.emplace_back(s.back() + v[i % len]);
int slen = s.size();
for (int i = 0; i < slen; ++i)
st[i][0] = s[i];
for (int j = 1; j <= log2(slen); ++j)
for (int i = 0; i < slen; ++i) {
st[i][j] = st[i][j - 1];
int right = i + (1 << (j - 1));
if (right < slen)
st[i][j] = min(st[i][j], st[right][j - 1]);
}
ll sum = s[len], hi_r = LO, hi_all = LO;
int r = k % len;
for (int i = 1; i < slen; ++i) {
if (r)
hi_r = max(hi_r, s[i] - query(max(0, i - r), i - 1));
hi_all = max(hi_all, s[i] - query(max(0, i - len), i - 1));
}
if (k < len)
return hi_r;
return max(hi_all, max(sum * (k / len - 1) + hi_all, sum * (k / len) + hi_r));
}

int main() {
cin >> n >> k;
vector<int> p(n), c(n);
for (int i = 0; i < n; ++i)
cin >> p[i];
for (int i = 0; i < n; ++i)
cin >> c[i];
ll ans = LO;
vector<bool> vis(n);
for (int i = 0; i < n; ++i) {
if (vis[i])
continue;
vector<int> v;
int idx = i;
while (!vis[p[idx] - 1]) {
idx = p[idx] - 1;
vis[idx] = true;
v.emplace_back(c[idx]);
}
ans = max(ans, solve(v));
}
cout << ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

# Problem E - Picking Goods (opens new window)

# 题目描述

$R$$C$列的方阵，其中有$K$个格子里有东西，第$i$个东西的价值为$v_i$。从左上角走到右下角，只能向下或向右走，限定每行最多拿$3$个东西，求能取得的最大价值。

# 题解

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

ll dp[3005][3005][4];

class Solution {
public:
void solve() {
int R, C, K;
vector<vector<int>> a(R + 1, vector<int>(C + 1));
memset(dp, 0, sizeof(0));
for (int i = 0; i < K; ++i) {
int r, c, v;
a[r][c] = v;
}
for (int i = 1; i <= R; ++i)
for (int j = 1; j <= C; ++j) {
for (int k = 0; k <= 3; ++k)
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][k]);
for (int k = 0; k <= 3; ++k)
dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k]);
if (a[i][j])
for (int k = 3; k > 0; --k)
dp[i][j][k] = max(dp[i][j][k], dp[i][j][k - 1] + a[i][j]);
}
ll ans = 0;
for (int i = 0; i <= 3; ++i)
ans = max(ans, dp[R][C][i]);
printf("%lld", ans);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

# Problem F - Making Palindrome (opens new window)

# 题目描述

$N$$N\leq50$）个长度不超过$L$$L\leq20$）的字符串，每个字符串可以使用无限次，第$i$个字符串使用一次的代价为$C_i$。问最少花费多少代价，能够用这些字符串组成一个回文串？或者说明无解。

# 题解

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define INF 10000000000000000LL

using namespace std;
typedef long long ll;

bool is_palindrome(string &s) {
int n = s.size();
for (int i = 0; i < n / 2; ++i)
if (s[i] != s[n - i - 1])
return false;
return true;
}

int n;
unordered_map<string, ll> memo[2];
unordered_set<string> vis[2];
vector<string> S[2];
vector<ll> C;
ll dfs(string s, int p) {
if (memo[p].count(s))
return memo[p][s];
if (is_palindrome(s))
return 0;
if (vis[p].count(s))
return INF;
vis[p].insert(s);
ll ans = INF;
int ls = s.size();
for (int i = 0; i < n; ++i) {
string t = S[!p][i];
int lt = t.size();
int l = min(ls, lt);
string ps = s.substr(0, l);
string pt = t.substr(0, l);
if (ps != pt)
continue;
ll cost =
ls > lt ? dfs(s.substr(l, ls - l), p) : dfs(t.substr(l, lt - l), !p);
if (cost < ans)
ans = min(ans, cost + C[i]);
}
vis[p].erase(s);
memo[p][s] = ans;
return ans;
}

int main() {
cin >> n;
S[0] = vector<string>(n);
S[1] = vector<string>(n);
C = vector<ll>(n);
ll ans = INF;
for (int i = 0; i < n; ++i) {
cin >> S[0][i] >> C[i];
S[1][i] = string(S[0][i].rbegin(), S[0][i].rend());
}
for (int i = 0; i < n; ++i)
ans = min(ans, dfs(S[0][i], 0) + C[i]);
cout << (ans == INF ? -1 : ans);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64