混合药剂问题描进，J0hn在上化学课，桌上有n瓶药剂

混合药剂( m i x )问题 描述 ：John 在上化学课，桌上有 n 瓶药剂，药剂一共有 100 种颜色，以 0~99 标号。John 想 要 把 所 有 的 药 剂 混 合 成 一 瓶 ， 但 他 每 次 只 能 把 相 邻 的 两 瓶 混 合 成 一 瓶 。如果混合的两瓶药剂的颜色分别为 a 和 b，那么混合后药剂的颜色为(a+b)%100，同 时 会 产 生 a*b 单 位 的 烟 雾 。 现 在 ， John 想 知 道 ， 把 所 有 药 剂 混 合 起 来 最 少 会产生多少单位的烟雾。输入 格式 ：第一行为正整数 t(≤10)，表示数据组数；每组数据中，第一行为正整数 n(≤100)；第二行为 n 个正整数 ci(<100)，表示每瓶药剂的颜色。输入 格式 ：对于每组数据，输出一个正整数，表示最少的烟雾量。

【以下回答由 GPT 生成】

解决方案:

1. 分析问题:
对于每组数据，我们需要找到一种最优的混合方式使得产生的烟雾量最少。

2. 设计算法:
我们可以使用动态规划的方法来解决这个问题。

首先定义一个二维数组dp，dp[i][j]表示将第i瓶药剂到第j瓶药剂之间混合的最少烟雾量。

然后我们可以递归地计算dp[i][j]的值，其中i < j。首先，我们找到一个分割点k，使得i <= k < j。我们可以将第i瓶药剂到第k瓶药剂之间混合成一瓶药剂，将第k+1瓶药剂到第j瓶药剂之间混合成一瓶药剂。这样的混合方式可以得到最少烟雾量，即dp[i][j] = dp[i][k] + dp[k+1][j] + c[i]*c[k+1]。我们遍历所有可能的分割点，找到最小的烟雾量即可。

最终的结果即为dp[0][n-1]。

3. 编写代码:

'''
def minimum_smoke(t, data):
    results = []
    for i in range(t):
        n = data[i][0]
        c = data[i][1]
        dp = [[0 for _ in range(n)] for _ in range(n)]

        for l in range(2, n+1):
            for i in range(0, n-l+1):
                j = i + l - 1
                dp[i][j] = float('inf')
                for k in range(i, j):
                    smoke = dp[i][k] + dp[k+1][j] + c[i]*c[k+1]
                    dp[i][j] = min(dp[i][j], smoke)

        results.append(dp[0][n-1])

    return results
'''

4. 复杂度分析:
设药剂瓶数为n，每组数据的时间复杂度为O(n^3)，空间复杂度为O(n^2)。

5. 测试样例:

**样例输入1:**
1
5
1 2 3 4 5

**样例输出1:**
59

**样例输入2:**
2
3
2 3 4
4
1 1 1 1

**样例输出2:**
18
8

【相关推荐】

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7630592

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

using namespace std;

int mix_drugs(int n, vector<int>& colors) {
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    for (int gap = 1; gap < n; gap++) {
        for (int i = 0; i < n - gap; i++) {
            int j = i + gap;
            dp[i][j] = INT_MAX;
            
            for (int k = i; k < j; k++) {
                int smoke = (colors[i] + colors[j]) % 100 + colors[i] * colors[j];
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + smoke);
            }
        }
    }
    
    return dp[0][n-1];
}

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        vector<int> colors(n);
        for (int i = 0; i < n; i++) {
            cin >> colors[i];
        }
        
        cout << mix_drugs(n, colors) << endl;
    }  
    return 0;
}