题目描述：
给你一个长度为 n 、下标从 0 开始的整数数组 nums ，表示收集不同巧克力的成本。每个巧克力都对应一个不同的类型，最初，位于下标 i 的巧克力就对应第 i 个类型。
在一步操作中，你可以用成本 x 执行下述行为：
- 同时修改所有巧克力的类型，将巧克力的类型
ith 修改为类型 ((i + 1) mod n)th。
假设你可以执行任意次操作，请返回收集所有类型巧克力所需的最小成本。
数据范围：
$1\le n \le 1000, 1\le x \le 10^9$
题解：
$n$ 的范围比较小，直接暴力枚举旋转次数，使用 $dp[i][j]$ 表示当前类型 $i$ 旋转 $j$ 次之后收取的最小代价。
这个地方不能加上旋转的共线，因为可能会有多个经过一次旋转之后同时达到了最小代价，如果加上旋转代价的话，这部分就会重复。
后面就直接枚举旋转了多少次，先加上旋转的贡献，然后再加上每个类型的最小代价。
代码：
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
long long minCost(vector<int> &nums, int x)
{
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n));
long long ans = LLONG_MAX;
for (int i = 0; i < n; ++i)
{
dp[i][0] = nums[i];
for (int j = 1; j < n; ++j)
{
dp[i][j] = min(dp[i][j - 1], nums[(i + j) % n]);
}
}
for (int j = 0; j < n; ++j)
{
long long tmp = 1ll * x * j;
for (int i = 0; i < n; ++i)
{
tmp += dp[i][j];
}
ans = min(ans, tmp);
}
return ans;
}
};
|