# week 5
## rock
### 解題思路
這題使用到了一個關鍵的技術 "單調堆疊"，該技術目的是維護一個裡面元素遞增或遞減的 Stack，來達成題目的要求。此外，這題的空間複雜度可以進一步壓到 O(N)，因為對於每個人，只要取得其拿到的石頭順序，便可以唯一決定她接下來的操作，故不需要在第一時間便像題目說明一樣直接做到底，而是可以先紀錄下一個人拿到的石頭順序就好，等到當前的人處理完後再處理下一個人即可。

時間複雜度: O(N^2)

### AC 程式

# include <stdio.h>
typedef long long int llt;

void StackPush(llt *Stack, llt* Top, llt val)
{
    (*Top)++;
    Stack[*Top]=val;
}

llt StackPop(llt *Stack, llt* Top)
{
    if(*Top==-1) return -1;

    (*Top)--;
    return Stack[*Top+1];
}

llt StackTop(llt *Stack, llt Top)
{
    if(Top==-1) return -1;

    return Stack[Top];
}

int main()
{
    llt n;
    scanf("%lld", &n);

    llt a[n];
    for(llt i=0;i<n;i++)
    {
        scanf("%lld", &a[i]);
    }

    llt Stack[n+10];
    llt Top=-1;

    llt aSize=n;
    llt ans=1;
    while(1)
    {
        llt a_next[n];
        llt a_nextSize=0;
        for(llt i=0;i<aSize;i++)
        {
            while(1)
            {
                if(StackTop(Stack, Top)==-1 || a[i]<=StackTop(Stack, Top)) break;
                a_next[a_nextSize]=StackPop(Stack, &Top);
                a_nextSize++;
            }
            StackPush(Stack, &Top, a[i]);
        }

        if(a_nextSize==0) break;

        for(llt i=0;i<a_nextSize;i++)
        {
            a[i]=a_next[i];
        }
        aSize=a_nextSize;
        ans++;

        while(StackTop(Stack, Top)!=-1)
        {
            StackPop(Stack, &Top);
        }

    }

    printf("%lld\n", ans);

    return 0;
}

## Signal
### 解題思路
用陣列實作堆疊，遇到相同的就把stack頂端pop掉。
### AC 程式

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(){
    char a[51],b[51];
    scanf("%s",a);
    int length = strlen(a);
    b[0] = a[0];
    int index = 1;
    for(int i = 1 ; i < length ; i++){
        if(a[i]==b[index-1]){
            index--;
        }
        else{
            b[index] = a[i];
            index++;
        }
    }
    b[index] = '\0';
    printf("%s\n",b);
    return 0;
}

## Mood_graph
### 解題思路
直接跑過每一種可能，並記錄下最好的那一種印出來。
### AC 程式

#include<stdio.h>
#include<stdlib.h>

int main(){
    int n ;
    scanf("%d",&n);
    int *old_graph = (int *)malloc(n*sizeof(int));
    int **new_graph = (int **)malloc(n*sizeof(int*));
    for(int i = 0 ; i < n ; i++){
        new_graph[i] = (int*)malloc(n*sizeof(int));
    }
    for(int i = 0 ; i < n ; i++){
        scanf("%d",&old_graph[i]);
    }
    int ans = 0,index = 0;
    for(int i = 0 ; i < n ; i++){//直接模擬每個點為山峰的情況
        new_graph[i][i] = old_graph[i];
        int sum = new_graph[i][i];
        for(int j = i ; j > 0 ;j--){
            if(old_graph[j-1] > new_graph[i][j]){
                new_graph[i][j-1] = new_graph[i][j];
            }
            else{
                new_graph[i][j-1] = old_graph[j-1];
            }
            sum += new_graph[i][j-1];
        }
        for(int j = i ; j < n-1 ;j++){
            if(old_graph[j+1] > new_graph[i][j]){
                new_graph[i][j+1] = new_graph[i][j];
            }
            else{
                new_graph[i][j+1] = old_graph[j+1];
            }
            sum += new_graph[i][j+1];
        }
    }

    printf("%d\n",ans);
    for(int i = 0 ; i < n ; i++){
        printf("%d ",new_graph[index][i]);
    }
    printf("\n");
    return 0;
}