**
試題 演算法訓練 擺動序列
**
資源限制
時間限制：1.0s 記憶體限制：512.0MB
問題描述
如果一個序列滿足下面的性質，我們就將它稱為擺動序列：
1. 序列中的所有數都是不大于k的正整數；
2. 序列中至少有兩個數，
3. 序列中的數兩兩不相等；
4. 如果第i – 1個數比第i – 2個數大，則第i個數比第i – 2個數小；如果第i – 1個數比第i – 2個數小，則第i個數比第i – 2個數大，
比如，當k = 3時，有下面幾個這樣的序列：
1 2
1 3
2 1
2 1 3
2 3
2 3 1
3 1
3 2
一共有8種，給定k，請求出滿足上面要求的序列的個數，
輸入格式
輸入包含了一個整數k，（k<=20）
輸出格式
輸出一個整數，表示滿足要求的序列個數，
樣例輸入
3
樣例輸出
8
前言：
博主大二菜鳥一枚，假期備考藍橋杯，第一次寫博客，希望能在博客中一起分享自己學到的東西，然后把學到的東西以自己理解的樣式更通俗地分享給大家，有不足的地方大家多多指正，和大佬們多多學習！
思路與想法：
首先這道題的思想是 dp動態規劃，所謂動態規劃是求解決策程序最優化的程序，往往是直接算出答案，而不是得出每一步得程序，
這道題并不能用遍歷的思想來思考，比如你打算遍歷每一種情況的序列，然后if滿足某種形式count++這種一定是不行的，資料太大會超時或效率太低并且很復雜
動態規劃都會用到二維陣列，并且需要多重的回圈來解題，這道題中我們會用到一個二維陣列dp[20][20]來儲存結果，具體下面會講到陣列的含義
那么這道題怎么去入手呢？
1、從題干中我們可以知道：每個序列中的數字數量一定大于等于2，并且小于等于k
例：k = 3時，序列可以是數量為2的1 2，也可以是數量為3的1 3 2（序列中的最大值不能大于k且最少為兩個數字）
2、那么我們可以去自己把k較小時的序列情況在紙上寫出來，找一些規律和思路（這往往是一些演算法題的精髓）
當k = 2時，只有數量為2的序列：12或 21兩種
當k = 3時，數量為2的序列:12, 13, 21, 23, 31, 32六種
數量為3的序列有213，231兩種
當k = 4時，數量為2的序列有12,13,14,21,23,24,31,32,34,41,42,43共12種
數量為3的序列有：213,214,314,324,231,241,341,342共8種
（我們這時不難發現小大小和大小大的情況數量一樣）
數量為4的序列有：2314，3241兩種（大小大小 和 小大小大各一種）
那么我們將這個結果總結為下圖：
（縱坐標代表k的值，橫坐標代表當前的k下，n個數字組成的序列的種數）
那么我們可以得出規律：
1、數字數量為2的序列一共有：k * (k - 1) 種
if(j == 2)
{
dp[i][j] = i * (i - 1);
}
2、對角線都是 2 種
else if(j == i)
{
dp[i][j] = 2;
}
3、其他情況下，dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
else
{
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}
4、我來解釋一下二維陣列dp[i][j]的含義，i代表k的值, j 代表序列中數字的個數
，那么我們這題的思路就是 把所有k情況下得結果都得出來，i = 2、3、4、5、6……，然后直接找到i == k時的dp[k][j]下每一個值相加再cout就好啦
for(int j=2;j<=k;j++)
{
answer+=dp[k][j]; //answer累加每一種的情況的數量
}
下面附完整代碼：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include<string.h>
using namespace std;
int main( )
{
int k,ans=0;
int dp[21][21];
memset(dp,0,sizeof(dp)); //初始化陣列
cin>>k;
int i,j,x;
for(i=2;i<=k;i++) // i : k=？的情況，最少兩個數字組成序列，所以i=2開始，最大不能大于k
{
for(j=2;j<=i;j++) // j : 序列有多少個數字，最少是兩個所以是j=2開始
{
if(j == 2) //兩個數字的情況
{
dp[i][j] = i * (i - 1);
}
else if(j == i) ///對角線的情況
{
dp[i][j] = 2;
}
else ///其他情況的時候
{
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}
}
}
for(x=2;x<=k;x++) ///輸出答案
{
ans+=dp[k][x]; //在k的情況下，相加每一種數量數字的種類
}
cout << ans; //輸出答案
return 0;
}
執行結果：
驗算：（52 == 20 + 20 + 10 + 2）
后語：本題還有另外解法：貪心等，想了解的可以去其他大佬那里學習哈哈，第一次寫博客肯定很多不足的地方希望大家發現問題了多多評判我會及時改正，有其他問題期待和大家一起交流！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/256445.html
標籤：其他