分金子（360公司2017春招真题）
题目描述
小明买了一些彩色的气球用绳子串在一条线上，想要装饰房间，每个气球都染上了一种颜色，每个气球的形状都是各不相同的。我们用1到9一共9个数字表示不同的颜色，如12345则表示一串5个颜色各不相同的气球串。但小明希望得到不出现重复颜色的气球串，那么现在小明需要将这个气球串剪成多个较短的气球串，小明一共有多少种剪法？如原气球串12345的一种是剪法是剪成12和345两个气球串。
注意每种剪法需满足最后的子串中气球颜色各不相同（如果满足该条件，允许不剪，即保留原串）。两种剪法不同当且仅当存在一个位置，在一种剪法里剪开了，而在另一种中没剪开。详见样例分析。
| 输入
测试数据包含多组输入数据。输入数据的第一行为一个正整数T(T<=20)，表示测试数据的组数。然后是T组测试数据，每组测试数据的第一行包含一个整数n，下一行包含n个数（n <= 500 ），表示每段金矿的含金量，保证其数值大小不超过1000。
| 样例输入
2 6 4 7 2 9 5 2 10 140 649 340 982 105 86 56 610 340 879
|
| 输出
对于每一组测试数据，输出一行"Case #id: sc1 sc2"，表示第id组数据时马贼A分到金子数量为sc1，马贼B分到金子数量为sc2。详见样例。
| 样例输出
Case #1: 18 11 Case #2: 3206 981
|
| 时间限制C/C++语言：1000MS其它语言：3000MS | 内存限制C/C++语言：65536KB其它语言：589824KB |
算法分析
动态规划，设F(L,R)为先手在[L,R]上所能取到的金子数，F(L,R)金子最大，即留给后手的金子最小，因此F(L,R) = sum(L,R) - min(F(L+1,R), F(L,R-1))。依次拆解，如([0,4])->([1,4], [0,3])->([2,4],[1,3],[0,2])->([3,4],[2,3],[1,2],[0,1])，记得要初始化F[i][i] = arr[i]。
由于sum(L,R) = sum(R)-sum(L-1)，会造成L溢出，因此将索引依次增加1。
提交代码：
#include
#includeusing namespace std;int main()
{int T;cin >> T;for (int t = 1; t <= T; ++t) {int n, number, temp = 0;vector arr, sum(1, 0);cin >> n;for (int i = 0; i < n; ++i) {cin >> number;temp += number;arr.push_back(number);sum.push_back(temp);}vector> golds(n+1, vector(n+1, 0));for (int i = 0; i < n; ++i) golds[i+1][i+1] = arr[i];for (int i = 1; i <= n; ++i) {for (int l = 1; l + i <= n; ++l) {int r = l + i;golds[l][r] = sum[r] - sum[l-1] - min(golds[l+1][r], golds[l][r-1]);}}cout << "Case #" << t << ": " << golds[1][n] << " " << sum[n] - golds[1][n] << endl;}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！