剪气球串（360）

2024-06-16 17:48

文章标签 360 气球

本文主要是介绍剪气球串（360），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

输入
第一行输入一个正整数n（1≤n≤100000），表示气球的数量。
第二行输入n个整数a1，a2，a3…an，ai表示该气球串上第i个气球的颜色。对于任意i，有1≤ai≤9。

样例输入
3
1 2 3

输出
输出一行，第一行输出一个整数，表示满足要求的剪法，输出最终结果除以1000000007后的余数。

样例输出
4

时间限制
C/C++语言：2000MS其它语言：4000MS
内存限制
C/C++语言：131072KB其它语言：655360KB

解题思路
题意理解为，将长度为n的，每位取值范围1-9的数组剪切子串，每个子串不能有重复的数字，问有多少种剪法。考虑用到动态规划，假设f(k)表示当长度为k时的剪法个数，他与f(k-1)什么关系呢？如果第k个数单独成一串，那么f(k)+=f(k-1)种剪法。若第k个数要与前面的m个成一串，必须要保证第k-m~k中没有重复的数，m最多取值为8,对应的f(k)+=f(k-m); 所以计算f(n)就是以此计算前f(1)…f(n-1)的值。

#include<stdio.h>
#include<cstring>
using namespace std;
const int MAX=100005;
const int M=1e9+7;
int main(){int n,data[MAX],dp[MAX];int state[10];记录n前1—9的位置是否有重复的情况//memset(dp,0,sizeof(dp));全局变量数组会默认吃初始为0dp[0]=1;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",data+i);}for(int i=1;i<=n;i++){memset(state,0,sizeof(state));for(int j=1;j<=i;j++){state[data[i-j]]++;if(state[data[i-j]]>1) break;dp[i]=(dp[i]+dp[i-j])%M;}}printf("%d",dp[n]%M);
}