[七－八点刷题2道]01

待我称王封你为后i 2022-03-10 06:17 119阅读 0赞

### 1. ###

/\* 题目描述  
如果一个数列S满足对于所有的合法的i,都有S\[i + 1\] = S\[i\] + d, 这里的d也可以是负数和零,我们就称数列S为等差数列。  
小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。小易允许在数列上做交换任意两个位置的数值的操作,并且交换操作允许交换多次。但是有些数列通过交换还是不能变成等差数列,小易需要判别一个数列是否能通过交换操作变成等差数列  
输入描述:  
输入包括两行,第一行包含整数n(2 ≤ n ≤ 50),即数列的长度。  
第二行n个元素x\[i\](0 ≤ x\[i\] ≤ 1000),即数列中的每个整数。  
输出描述:  
如果可以变成等差数列输出"Possible",否则输出"Impossible"。  
示例1  
输入  
复制  
3  
3 1 2  
输出  
复制  
Possible  
\*/

#include <bits/stdc++.h>
    using namespace std;
    int main(void)
    { 
        int n;
        cin >> n;
        vector<int> vv;
        int temp;
        while (n--)
        { 
            cin >> temp;
            vv.push_back(temp);
        }
        sort(vv.begin(), vv.end());
        int len = vv.size();
        int sum = 0, tt = vv[1] - vv[0];
        for (int i = 2; i < len; i++)
        { 
            if (tt != vv[i] - vv[i - 1])
            { 
                cout << "Impossible" << endl;
                return 0;
            }
            tt = vv[i] - vv[i - 1];
        }
        cout << "Possible" << endl;
    }

以上代码AC

### 2. ###

题目描述  
小Q和牛博士在玩一个石子合并的游戏，初始一共有n堆石子，每堆石子有w\[i\]个石子。小Q和牛博士他们需要对石子堆进行合并，每次他们可以任意选择两堆石子进行合并。一堆有x个石子的石子堆和一堆有y个石子的石子堆合并将得到一堆x+y个石子的石子堆，这次合并得分为x\*y，当只剩下一堆石子的时候游戏结束。

、小Q和牛博士希望采取优秀的策略获得最大得分，希望你能来帮他们算算最大得分多少。

输入描述:  
输入包括两行，第一行一个正整数n(2≤n≤100)。

第二行包括n个正整数wi，即每堆石子的个数。  
输出描述:  
输出一个正整数，即小Q和牛博士最大得分是多少。  
示例1  
输入  
复制  
3  
1 2 3  
输出  
复制  
11 \*/

#include <bits/stdc++.h>
    using namespace std;
    //贪心,两个两个student一个桌子的问题
    int main()
    { 
        int n;
        cin >> n;
        vector<int> vv;
        int temp;
        while (n--)
        { 
            cin >> temp;
            vv.push_back(temp);
        }
        sort(vv.begin(), vv.end());
        for (auto i : vv)
            cout << i << " ";
        cout << endl;
        int result = vv[0] * vv[1];
        int sum = 0;
        for (int i = 1; i < vv.size(); i++)
        { 
            sum += vv[i - 1];
            result += vv[i] * sum;
            cout << "v[i] = " << vv[i] << " " << sum << " " << result << endl;
        }
        cout << result - 1 << endl;
    }

以上代码AC 70%

##### 别人通过的代码： #####

#include <iostream>
     
    using namespace std;
     
    int main() { 
        int n; cin >> n;
        int stock = 0, score = 0;
        for(int curr; cin >> curr; ) { 
            score += stock * curr;
            stock += curr;
        }
        cout << score;
    }

证明：  
其实顺序完全不影响的。无论什么顺序都是一样的结果。

设w1,w2,…,wn是一个任意的合并顺序（即先取w1，之后w1和w2合并，再之后w1 + w2,w3合并……）  
在该合并顺序下的得分为：  
![在这里插入图片描述][20190309215030848.png]  
将上面的式子乘以二，再将含有w1,w2,…wn的项提出来（把下面的和上面的对比你会发现每一个都多用了一遍），得到：  
![在这里插入图片描述][20190309215050384.png]  
记![在这里插入图片描述][20190309215120987.png]，那么其实总得分就是![在这里插入图片描述][20190309215136268.png] ，**与具体序列的顺序无关，只与序列元素的值有关。**

### 刷题总结： ###

##### (2)石子合并的问题： #####

*  第一种

n堆石子，每次合并的花费为两堆石子数目之和，求怎样合并可以使得合并为一整堆石子的总花费最少

实际上这就是HUfffman编码的变形，运用贪心策略，每次找出最小的两堆合并即可。

*  第二种

描述与第一种很相似，只不过每次合并只能合并相邻的两堆石子

那么贪心策略就不一定有用，局部最优的结果不一定是全局最优

那么我们就要考虑了，全局最优的子结构也应当是最优的。那么，我们就要考虑动态规划了，

状态转移方程：

`dp[i][j] = min(dp[i][j],d[i][k]+dp[k+1][j]+sum[j]-sum[i])`

解释一下，dp\[i\]\[j\]表示合并第i堆到第j堆石子的最小花费，k的取值范围为i到j之间，表示分割点，例如1-3就可以分为1-2与3-3，sum【i】表示前i堆石子的总重量

初始化dp\[i\]\[i\]为0，其他为无穷大

*  (3)问题(2)的是在石子排列是直线情况下的解法，如果把石子改为环形排列，又怎么做呢？

参考：  
[https://zhuanlan.zhihu.com/p/44251303][https_zhuanlan.zhihu.com_p_44251303]  
[https://blog.csdn.net/gatieme/article/details/49206193][https_blog.csdn.net_gatieme_article_details_49206193]

[20190309215030848.png]: /images/20220310/887da58057ed46428d31a82d5e7778b6.png
[20190309215050384.png]: /images/20220310/442327cefaaa476d8e4a6c8acf0b87f0.png
[20190309215120987.png]: https://img-blog.csdnimg.cn/20190309215120987.png
[20190309215136268.png]: /images/20220310/c8f42535942240e987c01122d908711d.png
[https_zhuanlan.zhihu.com_p_44251303]: https://zhuanlan.zhihu.com/p/44251303
[https_blog.csdn.net_gatieme_article_details_49206193]: https://blog.csdn.net/gatieme/article/details/49206193