剪气球串

84 阅读 0 评论 56 点赞

我是靠谱客的博主幸福丝袜，这篇文章主要介绍剪气球串，现在分享给大家，希望可以做个参考。

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

这里写图片描述

这是2017年360的春招题，利用动态规划的思想可以很巧妙得解决这个问题。

用dp[n]来表示a[1],a[2],a[n]所组成的字符串可能的最多剪法。
算法思想：
1.计算dp[n]的时候，因为 a[n]可以独立出来，单独作为一组，所以
dp[n]=dp[n-1];
2.如果a[n]和a[n-1]不同
dp[n]+=dp[n-2]; //a[n]和a[n-1]可以组成一组
3.枚举a[n]前的至多8个数字，如果不等，那么dp[n]+=dp[n-j];
4. 初始条件：dp[0]=1;

复制代码

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
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++)
cin>>a[i];
int dp[n+1];
memset(dp,0,sizeof(dp));
dp[0]=1;
int cnt[9];
for(int i=1;i<=n;i++){
memset(cnt,0,sizeof(cnt));
for(int j=i;j>=1;j--){
cnt[a[j]]++;
if(cnt[a[j]]>1)
break;
dp[i]=(dp[i]+dp[j-1])%1000000007;
}
}
cout<<dp[n]<<endl;
return 0;
}