剪气球串（360公司2017春招真题）

题目描述

小明买了一些彩色的气球用绳子串在一条线上，想要装饰房间，每个气球都染上了一种颜色，每个气球的形状都是各不相同的。我们用1到9一共9个数字表示不同的颜色，如12345则表示一串5个颜色各不相同的气球串。但小明希望得到不出现重复颜色的气球串，那么现在小明需要将这个气球串剪成多个较短的气球串，小明一共有多少种剪法？如原气球串12345的一种是剪法是剪成12和345两个气球串。
注意每种剪法需满足最后的子串中气球颜色各不相同（如果满足该条件，允许不剪，即保留原串）。两种剪法不同当且仅当存在一个位置，在一种剪法里剪开了，而在另一种中没剪开。详见样例分析。

算法分析

动态规划，考虑前i个有多少种剪法，枚举最后剪的一段转移。

提交代码：

#include<iostream>
#include<vector>

using namespace std;
const int M = 1e9 + 7;

int main()
{
	int n, number;
	cin >> n;
	vector<int> arr, result(n, 0);
	result[0] = 1;
	for (int i = 0; i < n; ++i) {
		cin >> number;
		arr.push_back(number);
	}

	for (int i = 1; i < n; ++i) {
		vector<int> state(10, 0);
		++state[arr[i]];
		// i单独情况
		result[i] = result[i - 1];
		// 和j分在一起
		for (int j = i - 1; j >= 0; --j) {
			++state[arr[j]];
			if (state[arr[j]] > 1) break;
			if (j == 0) ++result[i];
			else result[i] = (result[i] + result[j - 1]) % M;
		}
	}
	cout << result[n - 1] << endl;
}

最后

以上就是繁荣朋友为你收集整理的剪气球串（360公司2017春招真题）的全部内容，希望文章能够帮你解决剪气球串（360公司2017春招真题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。