Catalog

Preface

Topic introduction

sample input :

sample output :

introduce ：

The theory exists , Practice begins ！

  Foundation tower （ Number triangle problem ）

Similar to this topic  

Precautions for this topic ： 

​Love is worth years. Love is worth years .

Preface

About several towers dp                              

Topic introduction

sample input :

6
5 1
4 1
6 1
7 2
7 2
8 3
0

sample output :

4

Before starting, you can write it yourself to see if you can write it yourself ~ Pay attention to the output format ！

introduce ：

I want to understand that it is a number tower pushed forward from the end ？？ The final output dp[0][5] The value of is not good ？ Okay , Is not dynamic planning    ：》

The theory exists , Practice begins ！

  Foundation tower （ Number triangle problem ）

Topic introduction ：

  sample input ：

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

  sample output ：

30

#include <stdio.h>
int max (int a,int b);
int max (int a,int b)
{
    if(a>b) return a;
    else return b;
    }
int main()
{
    int n;
    scanf("%d",&n);
    int max_sum[n][n];
    int d[n][n];;
    int i,j;
    for (i=0;i<n;i++)
    {
        for(j=0;j<=i;j++)
        {
            scanf("%d",&d[i][j]);
        }
    }
    for (j=0;j<n;j++)
    {
        max_sum[n-1][j]=d[n-1][j];
    }
    for (i=n-2;i>=0;i--)
        for (j=0;j<i+1;j++)
        {
            max_sum[i][j]=d[i][j]+max(max_sum[i+1][j],max_sum[i+1][j+1]);
        }
    printf("%d",max_sum[0][0]);
}

Similar to this topic  

#include <stdio.h>
#include <string.h>
int max (int a,int b,int c)
{
    int max=a;
    if(b>max)max=b;
    if(c>max)max=c;
    return max;
}
int max_t(int a,int b)
{
    if(a>b)return a;
        else return b;
}
int dp[100010][12];
 int a[100010][12];// Line represents time , The list shows the pie over there .

int main()
{
    int n;
    int x,t;
    int i,j;
    int maxt=0;
     
    while(scanf("%d",&n)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        if(n==0)break;
        for (i=0;i<n;i++)
        {
            scanf("%d%d",&x,&t);
            a[t][x]++;
            if(t>maxt)maxt=t;
        }
        for (j=0;j<=10;j++)
            {
                dp[maxt][j]=a[maxt][j];
            }
        for (i=maxt-1;i>=0;i--)
        {
            for (j=0;j<=10;j++)
            {
                if(j==0) dp[i][j]=max_t(dp[i+1][j],dp[i+1][j+1])+a[i][j];
                    else
                dp[i][j]=max(dp[i+1][j],dp[i+1][j+1],dp[i+1][j-1])+a[i][j];
            }
        }
        printf("%d\n",dp[0][5]);
    }
}

Precautions for this topic ： 

1. Reset the array after each group of input memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); The operation of .

2. Want to consider j==0 The situation may lead to errors

3. Don't consider the right endpoint because we set it all to 0 了 .

4. Stack storage will report an error -1073741571 (0xC00000FD) That is, the array is too large , You can use global variables or structure definitions to solve

Love is worth years.
Love is worth years .