9도 OJ 1407(DP) 1408(DP) 1409(DP) 1410(DP) 1411(최단로)

1407: 최소수점 찾기

제목의 뜻

크기가 N인 정수 배열array를 지정하고 두 가지 동작을 정의합니다: 1) Add (L, R, W).하위 배열 [L, R]의 요소를 정수 W로 누적합니다.2) Min(L, R).하위 배열 [L, R]에서 가장 작은 요소의 값을 반환합니다.여기서 L 및 R은 배열의 아래 첨자이며 카운트는 0부터 시작합니다.배열에 L > R을 표시할 때 우리는 이 하위 배열의 요소가array[L],array[L+1],...array[N-1],array[0],array[1],...array[R]를 포함한다고 생각한다.

사고의 방향

구간 조회의 최소치 문제는 일반적으로 라인 트리로 해결하고 요구가 높지 않은 경우 분통법(즉 제곱분할)도 사용할 수 있다.

코드

#include <stdio.h>
#include <limits.h>

#define N 100000
#define M 100
#define INF INT_MAX

int a[N];
int seg[4*N];
int add[4*N];

int min(int x, int y)
{
    return (x < y) ? x : y;
}

void pullup(int i)
{
    seg[i] = min(seg[2*i], seg[2*i+1]);
}

void pushdown(int i)
{
    if (add[i])
    {
        add[2*i] += add[i];
        add[2*i+1] += add[i];
        seg[2*i] += add[i];
        seg[2*i+1] += add[i];
        add[i] = 0;
    }
}

void create(int i, int b, int e)
{
    add[i] = 0;
    if (b == e)
    {
        seg[i] = a[b];
        return;
    }
    create(2*i, b, (b+e)/2);
    create(2*i+1, (b+e)/2+1, e);
    pullup(i);
}

void update(int w, int i, int b, int e, int l, int r)
{
    //printf("%d %d %d %d %d
", i, b, e, l, r);
    //printf("=====");
    //for (int j=0; j<11; j++)
    //  printf("%d ", seg[j]);
    //printf("
");
    //for (int j=0; j<11; j++)
    //  printf("%d ", add[j]);
    //printf("
");
    if (b > r || e < l)
        return;
    if (l <= b && e <= r)
    {
        add[i] += w;
        seg[i] += w;
        return;
    }
    pushdown(i);
    update(w, 2*i, b, (b+e)/2, l, r);
    update(w, 2*i+1, (b+e)/2+1, e, l, r);
    pullup(i);
}

int getMin(int i, int b, int e, int l, int r)
{
    if (b > r || e < l)
        return INF;
    if (l <= b && e <= r)
    {
        return seg[i];
    }
    pushdown(i);
    int m1 = getMin(2*i, b, (b+e)/2, l, r);
    int m2 = getMin(2*i+1, (b+e)/2+1, e, l, r);
    //pullup(i);
    return min(m1, m2);
}

int main(void)
{
    int n, i, m;
    char s[M];
    int l, r, w;

    while (scanf("%d", &n) != EOF)
    {
        for (i=0; i<n; i++)
            scanf("%d", &a[i]);
        create(1, 0, n-1);

        scanf("%d", &m);
        getchar();
        for (i=0; i<m; i++)
        {
            scanf("%d%d", &l, &r);
            gets(s);
            if (s[0] == '\0')
            {
                if (l > r)
                {
                    int m1 = getMin(1, 0, n-1, l, n-1);
                    int m2 = getMin(1, 0, n-1, 0, r);
                    printf("%d
", min(m1, m2));
                }
                else
                    printf("%d
", getMin(1, 0, n-1, l, r));
            } 
            else
            {
                sscanf(s, "%d", &w);
                if (l > r)
                {
                    update(w, 1, 0, n-1, l, n-1);
                    update(w, 1, 0, n-1, 0, r);
                }
                else
                    update(w, 1, 0, n-1, l, r);
            }
        }
    }

    return 0;
}   
/**************************************************************
    Problem: 1407
    User: liangrx06
    Language: C
    Result: Accepted
    Time:360 ms
    Memory:4432 kb
****************************************************************/

1408:콩 먹는 로봇

제목의 뜻

타오바오 회사 내부에는 많은 신선한 작은 장난감이 있는데 예를 들면 타오바오 스마트 로봇이다.어렸을 때 모두들 그 콩을 먹는 놀이를 해 봤죠. 이 로봇은 이 놀이에 따라 설계된 거예요. 콩을 향해 걸어가요.그러나 로봇은 남쪽과 동쪽으로만 걷는 버그가 하나 더 있다.지금은 공터가 하나 있는데 n*m의 칸으로 나뉘어 있고 칸마다 콩이 하나 있다.로봇의 출발점은 서북쪽에 있고, 종점은 동남쪽에 있다.로봇은 시작점부터 끝점까지 몇 가지 다른 방법이 있습니까?

사고의 방향

간편한 DP그러나 사실 조합수 공식으로 직접 답을 제시할 수도 있지만 n과 m가 너무 커서 아직 이런 큰 조합수 추출 계산 방법을 파악하지 못했다.

코드

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

#define N 1000
#define M 10009

int main(void)
{
 int n, m, i, j;
 int a[N+1][N+1];

 memset(a, 0, sizeof(a));
 for (i=1; i<=1000; ++i)
 a[1][i] = a[i][1] = 1;
 for(i=2; i<=N; i++)
 {
 for (j=2; j<=N; j++)
 {
 a[i][j] = (a[i-1][j]+a[i][j-1]) % M;
 }
 }

 while (scanf("%d%d", &n, &m) != EOF)
 {
 printf("%d
", a[n][m]);
 }

 return 0;
}
/**************************************************************
 Problem: 1408
 User: liangrx06
 Language: C
 Result: Accepted
 Time:20 ms
 Memory:4752 kb
****************************************************************/

1409：TBString

제목의 뜻

타오바오 회사 내부에 문자열이 하나 있는데, 그는 평소에 심심해서 문자열을 연구한다.어느 날, 그는 문자열 TBBT를 연구할 때 통계 함수 F를 정의했다. F(S)는 문자열에 S가 나타난 횟수를 나타낸다.문자열 TBTBT의 경우 F(T)=3, F(B)=3, F(TB)=2, F(BT)=2가 있습니다.그러나 만약 우리가 F (T), F (B), F (TB) 와 F (BT) 네 개의 값을 알고 있다면, 당신은 이 네 가지 조건을 충족시키고 사전 순서가 가장 작은 문자열을 구할 수 있습니까?존재하면 이 문자열 출력하기;존재하지 않으면 -1을 출력합니다.주의해야 할 것은 문자열 어린 왕자는 T가 B보다 작다고 생각한다. 왜냐하면 B가 T보다 작으면 문자열의 시작이 BTB일 수도 있기 때문이다. 하하, 너희들은 사악하겠지.

사고의 방향

이 문제는 DP에 속해야 하기 때문에 사고방식은 어렵지 않지만 정말 귀찮아서 여러 가지 가능한 상황에 주의해야 한다.다행히 AC가 한 번 나왔으니 망정이지, 그렇지 않았다면 정말 틀렸을 텐데, 조사하고 싶지 않았다.

코드

#include <stdio.h>

int main()
{
    int i;
    int t, b, tb, bt;
    char s[2000001];

    while (scanf("%d%d%d%d", &t, &b, &tb, &bt) != EOF) {
        int flag = 1;
        if (tb == bt) {
            if (t < tb || b < tb)
                flag = 0;
            else if (t == tb && b == tb)
                flag = 0;
            else if (t == tb) {
                int k = 0;
                for (i = 0; i < t; i ++)
                    s[k++] = 'B', s[k++] = 'T';
                for (i = 0; i < b-tb; i ++)
                    s[k++] = 'B';
                s[k] = '\0';
            }
            else {
                int k = 0;
                for (i = 0; i < t-tb; i ++)
                    s[k++] = 'T';
                for (i = 0; i < tb; i ++) {
                    s[k++] = 'B';
                    if (i == tb-1) {
                        for (int j = 0; j < b-tb; j ++)
                            s[k++] = 'B';
                    }
                    s[k++] = 'T';
                }
                s[k] = '\0';
            }
        }
        else if (tb > bt) {
            if (tb != bt+1 || t < tb || b < tb)
                flag = 0;
            else {
                int k = 0;
                for (i = 0; i < t-tb; i ++)
                    s[k++] = 'T';
                for (i = 0; i < tb; i ++)
                    s[k++] = 'T', s[k++] = 'B';
                for (i = 0; i < b-tb; i ++)
                    s[k++] = 'B';
                s[k++] = '\0';
            }
        }
        else {
            if (tb != bt-1 || t < bt || b < bt)
                flag = 0;
            else {
                int k = 0;
                for (i = 0; i < bt; i ++) {
                    s[k++] = 'B';
                    if (i == bt-1) {
                        for (int j = 0; j < b-bt; j ++)
                            s[k++] = 'B';
                    }
                    s[k++] = 'T';
                    if (i == 0) {
                        for (int j = 0; j < t-bt; j ++)
                            s[k++] = 'T';
                    }
                }
                s[k] = '\0';
            }
        }
        if (flag == 0)
            puts("-1");
        else
            puts(s);
    }

    return 0;
}
/************************************************************** Problem: 1409 User: liangrx06 Language: C Result: Accepted Time:90 ms Memory:2792 kb ****************************************************************/

1410:적목 쌓기

제목의 뜻

너에게 장방체의 적목을 줄 테니, 아래의 규칙에 따라 가장 많은 적목을 쌓을 수 있는지 물어봐라.한 개의 적목 위에 최대 한 개의 적목만 쌓을 수 있다.2 아래의 적목의 길이는 위의 적목의 길이보다 크거나 같다

사고의 방향

처음에는 DP를 쓸 생각을 하지 못했는데 좋은 생각이 없었다.다른 사람이 DP를 쓰는 것을 보고서야 아주 간단하다는 것을 알았다.

코드

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

#define N 1000000
#define M 100

int max(int a, int b)
{
 return (a>b) ? a : b;
}

int dp[M+1][M+1][M+1];
int count[M+1][M+1][M+1];

int main(void)
{
 int n, i, j, k, r, m;
 int len, wid, heig;

 while (scanf("%d", &n) != EOF)
 {
 memset(count, 0, sizeof(count));
 for (i=0; i<n; i++)
 {
 scanf("%d%d%d", &len, &wid, &heig);
 count[len][wid][heig] ++;
 }

 memset(dp, 0, sizeof(dp));
 m = 0;
 for (j=1; j<=M; j++)
 {
 for (k=1; k<=M; k++)
 {
 for (r=1; r<=M; r++)
 {
 dp[j][k][r] = max(max(dp[j-1][k][r], dp[j][k-1][r]),
 dp[j][k][r-1]) + count[j][k][r];
 m = max(m, dp[j][k][r]);
 }
 }
 }
 printf("%d
", m);
 }

 return 0;
}
/**************************************************************
 Problem: 1410
 User: liangrx06
 Language: C
 Result: Accepted
 Time:1210 ms
 Memory:8964 kb
****************************************************************/

1411:턴

제목의 뜻

지향도에 n개의 정점(번호 1부터 n까지)이 있는데 기점 s를 주고 기점에서 출발하면 적어도 한 변을 지나 기점의 가장 짧은 거리로 돌아간다.

사고의 방향

주체는 dijkstra 알고리즘으로 해답을 구하지만 제목은 최소한 한 변을 거쳐야 하기 때문에 기점이 직접 연결된 모든 변을 초기화해야 하며 다른 (기점 포함)의 값은 무궁무진하다.

코드

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

#define INF 100000000
#define N 501

int main()
{
    int n, m, s, a, b, c, map[N][N], len[N], used[N];
    while (scanf("%d%d%d", &n, &m, &s) != EOF)
    {
        memset(map, 0, sizeof(map));
        while (m--)
        {
            scanf("%d%d%d", &a, &b, &c);
            if (map[a][b]==0 || map[a][b]>c)
                map[a][b] = c;
        }

        for(int i=1; i<=n; i++)
            if(map[s][i] != 0)
                len[i] = map[s][i];
            else
                len[i] = INF;
        int index, min;
        memset(used, 0, sizeof(used));
        while(1)
        {
            min = INF, index = -1;
            for(int i=1; i<=n; i++)
                if(!used[i] && len[i] < min)
                    min = len[i], index = i;
            if(index == -1 || index == s)
                break;
            used[index] = 1;
            for(int i = 1;i <= n; i++)
                if(!used[i] && map[index][i] && len[i] > len[index] + map[index][i])
                    len[i] = len[index] + map[index][i];
        }
        if(index == -1)
            printf("help!
");
        else
            printf("%d
", len[s]);
    }
}
/**************************************************************
    Problem: 1411
    User: liangrx06
    Language: C
    Result: Accepted
    Time:120 ms
    Memory:1828 kb
****************************************************************/