当前位置：首页 > news >正文

动态规划- 【气球游戏】

news 2025/6/6 11:52:46

题目：【气球游戏】小Q在进行射击气球的游戏，如果小Q在连续T枪中打爆了所有颜色的气球，将得到一只QQ公仔作为奖励。（每种颜色的气球至少被打爆一只）。这个游戏中有m种不同颜色的气球，编号1到m。小Q一共有n发子弹，然后连续开了n枪。小Q想知道在这n枪中，打爆所有颜色的气球最少用了连续几枪？
输入描述：
第一行两个空格间隔的整数数n，m。n<=1000000 m<=2000
第二行一共n个空格间隔的整数，分别表示每一枪打中的气球的颜色,0表示没打中任何颜色的气球。
输出描述：
一个整数表示小Q打爆所有颜色气球用的最少枪数。如果小Q无法在这n枪打爆所有颜色的气球，则输出-1
示例
输入：
12 5
2 5 3 1 3 2 4 1 0 5 4 3
输出：
6

二、思路：

1.暴力求解：冒泡排序的方式遍历击中气球序列arr_ball[2000]，对每个子串i...j范围进行判断是否击中所有颜色气球，全部击中所有颜色则赋值击中次数shut_cnt。复杂度o(n^3)

2.对问题进行抽象：个人认为分两步

1）找出所有包含1~m数字的子数组序列，这种序列的特点是子数组的和大于等于 (1+...+m)且包含1...m数字,可以抽象成求数组序列子段和大于某一阈值问题。

2）找出子数组长度最短的序列长度。

暴力求解代码c++：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
// 返回是否击中所有颜色，赋值击中次数shut_cnt 
bool loop_m(int i,int j ,int arr_ball[],int m,int &shut_cnt)
{int sum_m=0,is_shut=1;int tmp_m[200]={0};for(int k=i;k<=j;k++){//没有击中任何颜色，设计次数+1if(arr_ball[k]==0 ) sum_m=1;else tmp_m[arr_ball[k]-1]+=1;}for(int j=0;j<m;j++){  //命中次数sum_m+=tmp_m[j];  //是否所有颜色命中,如果有遗漏则，则该组命中次数设置为0if(tmp_m[j]==0) is_shut=0;}shut_cnt+=sum_m;return is_shut!=0 ? true : false ;}
int is_vector(int n,int m, int arr_ball[])
{int i=0,j=0,cur_min=0,min=10000;//for(int i=0;i<m;i++) i+=tmp_m[i]; //memset(&tmp_m,0,sizeof(tmp_m));for( i=0 ;i<n-1;i++){for(j=i+1;j<n;j++){//长度>=m的子序列if(j-i+1>=m){    //当前击中次数cur_min=0;//子序列中是否有满足击中所有颜色气球if(loop_m(i,j,arr_ball,m,cur_min)==true){if(cur_min<min)min=cur_min;}}}}}return (min >=m && min!=10000)? min : -1 ;}int main() {int n,m,arr_ball[2000];cin >> n>> m;for(int i=0;i<n;i++) cin>>arr_ball[i];cout << is_vector(n,m,arr_ball) << endl;
}

结果：

测试用例1

12 5
2 5 3 1 3 2 4 1 0 5 4 3

结果：